binary-search-tree.c

// Online C compiler to run C program online
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
    int info;
    struct node* left;
    struct node* right;
};
typedef struct node node;
typedef node* Tree;

void initTree(Tree* root_ref) {
    *root_ref = NULL;
}

void destroyTree(Tree root) {
    if (root == NULL) return;
    destroyTree(root->left);
    destroyTree(root->right);
    free(root);
}

void TraverseLNR(Tree root) {
    if (root == NULL) return;
    TraverseLNR(root->left);
    printf("%d ", root->info);
    TraverseLNR(root->right);
}
 
void TraverseLRN(Tree root) {
    if (root == NULL) return;
    TraverseLRN(root->left);
    TraverseLRN(root->right);
    printf("visit %d\n", root->info);
}

void TraverseNLR(Tree root) {
    if (root == NULL) return;
    printf("visit %d\n", root->info);
    TraverseNLR(root->left);
    TraverseNLR(root->right);
}

node* NewNode(int k) {
    node* temp = (node*) malloc (sizeof(node));
    if (temp == NULL) exit(1);
    temp->info = k;
    temp->left = temp->right = NULL;
    return temp;
}

 void AddNodeBST(Tree* root_ref, int k) {
    Tree root = *root_ref;
    Tree curr = root; Tree prev = NULL;
    while (curr != NULL) { // find
        prev = curr;  // update prev for the NEXT loop
        if (k == curr->info) return;
        else if (k < curr->info) curr = curr->left;
        else curr = curr->right;
    }
    Tree new_node = NewNode(k);
    if (prev == NULL) root = new_node; // null tree
    else if (k < prev->info) prev->left = new_node;
    else prev->right = new_node;
    *root_ref = root;
}

bool Exist(int x, int A[], int n) {
    for (int i = 0; i < n; i++)
        if (x == A[i]) return true;
    return false;
}

void CreateBST(Tree* root_ref, int n) {
    int A[n]; int k = 0; srand(time(NULL));
    for (int i = 0; i < n; i++) {
        do {
            k = rand() % 10;
        } while (Exist(k, A, i));
        A[i] = k;
    }
    for (int i = 0; i < n; i++)
        AddNodeBST(root_ref, A[i]);
}

int DemNutLa(Tree root) {
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL) {
        return 1;
    } else {
        return DemNutLa(root->left) + DemNutLa(root->right);
    }
}

int DemNutLaChan(Tree root) {
    if (root == NULL) {
        return 0;
    }
    else if (root->left == NULL && root->right == NULL) {
        if (root->info % 2 == 0) return 1;
        else return 0;
    } else {
        return DemNutLaChan(root->left) + DemNutLaChan(root->right);
    }
}

int Tong(Tree root) {
    if (root == NULL) {
        return 0;
    } else {
        return root->info + Tong(root->left) + Tong(root->right);
    } 
}

int TongChan(Tree root) {
    if (root == NULL) {
        return 0;
    } else {
        int k = 0;
        if (root->info % 2 == 0) k = root->info;
        return k + TongChan(root->left) + TongChan(root->right);
    } 
}


int main() {
    Tree root;
    initTree(&root);
    CreateBST(&root, 5);
    TraverseLNR(root);
    printf("\n%d ", TongChan(root));
    return 0;
}