tree.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
struct node{
    int key;
    node *left, *right;
};
 
#define max(x,y) (x > y ? x : y)
void tree_insert_node(node* &root, node* p){
    if (root != NULL){
        if (root->key == p->key) return ;
        else if (root->key > p->key){
            return tree_insert_node(root->left, p);
        }
        else return tree_insert_node(root->right, p);
    }
    root = p;
}
node* create_node(int x){
    node* p = (node*)malloc(sizeof(node));
    p->key = x;
    p->left = p->right = NULL;
    return p;
}
 
node* search(node* root, int x){
    node* p = root;
    while(p != NULL){
        if (p->key == x) return p;
        else if(x > p->key) p = p->right;
        else p = p->left;
    }
    return NULL;
}
 
void traverse_NLR(node *root){
    if (root != NULL){
        printf("%d ", root->key);
        traverse_NLR(root->left);
        traverse_NLR(root->right);
    }
}
 
int dem_la(node* root){
    if (root == NULL) return 0;
 
    return dem_la(root->left) + dem_la(root->right)
            + ((!root->left && !root->right ) ? 1 : 0);
}
 
int co_1_con(node* root){
    return (root->left == NULL && root->right != NULL)
        || (root->left != NULL && root->right == NULL);
}
int dem_node_co_1_con(node* root){
    if (root == NULL) return 0;
 
    return dem_node_co_1_con(root->left) + dem_node_co_1_con(root->right)
            + ( co_1_con(root) ? 1 : 0);
}
 
int la_so_ngto(int n){
    return 1;
}
int dem_node_la_so_ngto(node* root){
    if (root == NULL) return 0;
 
    return dem_node_la_so_ngto(root->left) + dem_node_la_so_ngto(root->right)
            + ( la_so_ngto(root->key) ? 1 : 0);
}
 
 
int max_chia_het(node* root){
    if (root == NULL) return -1;
    return max(max(max_chia_het(root->left)
            , max_chia_het(root->right))
        , (root->key % 9 == 0 ? root->key : -1));
}
node* max_dk(node* root){
	if (root == NULL) return NULL;
	node* l = max_dk(root->left);
	node* r = max_dk(root->right);

	node* max = NULL;

	if (l != NULL){
		if (r != NULL){
			if ( l->key > r->key) max = l;
			else max = r;
		}
		else max = l;
	}
	else if (r!= NULL) max = r;

	if (ktr_dk(root) && root->key > max->key)

}

void max_chia(node* root, int &max){
    if (root != NULL){
        if (root->key % 9 == 0 && root->key > max){
            max = root->key;
        }
        max_chia(root->left, max);
        max_chia(root->right, max);
    }
}
 
int in_theo_muc(node* root, int muc){
    if (root != NULL){
        int a = 0;
        if (muc == 0){
            printf("%d ", root->key);
            a = 1;
        }
        a += in_theo_muc(root->left, muc -1);
        a += in_theo_muc(root->right, muc -1);
        return a;
    }
    return 0;
}
 
void xoa_sach(node* &root){
    if (root != NULL){
        xoa_sach(root->left);
        xoa_sach(root->right);
        free(root); root = NULL;
    }
}
 
void ThayThe(node* &p, node* &T)
{
    if(T->left!=NULL) ThayThe(p,T->left);
    else
    {
        p->key = T->key;
        p=T;
        T=T->right;
    }
}
void DeleteNode(node* &T)
{
    if(T!=NULL)
    {
        node *p;
        p=T;
        if (T->left==NULL) T = T->right;
        else if(T->right==NULL) T=T->left;
        else ThayThe(p, T->right);
 
        free(p);
    }
}
 
void delete_key(node* &TREE, int  key){
    /*while(TREE!= NULL){
        if (TREE->key > key)
            ft;
        else if (TREE->key > key) TREE = TREE->right;
        DeleteNode(TREE);
    }*/
    if (TREE){
        if(key > TREE->key) delete_key(TREE->right, key);
        else if (key < TREE->key) delete_key(TREE->left, key);
        else DeleteNode(TREE);
    }
}
 
void delete_gtx(node* &TREE, int x){
    if (TREE){
        while(TREE->key > x) DeleteNode(TREE);
        delete_gtx(TREE->left, x);
        delete_gtx(TREE->right, x);
    }
}
void copy_cay(node* tree1, node* &tree2){
    if (tree1){
        node *p = create_node(tree1->key);
        tree2 = p;
        copy_cay(tree1->left, tree2->left);
        copy_cay(tree1->right, tree2->right);
    }
}
 
int main (){
    srand(2);
    node* TREE = NULL;
    node* TREE2 = NULL;
 
    for (int i = 0; i < 12; i++){
        node*p = create_node(rand()%50);
        //printf("%d ", p->key);
        tree_insert_node(TREE, p);
 
    }
    printf("\n OUR TREE: ");
    traverse_NLR(TREE);

	printf("So node la la %d \n", dem_node_co_1_con(TREE));
	return 0;

    //delete_key(TREE, 19);
    delete_gtx(TREE, 15);
    printf("in theo chieu rong: \n");
    for(int i = 0; in_theo_muc(TREE, i)!= 0; i++){
        printf("\n");
    }
 
 
 
    if (TREE2) xoa_sach(TREE2);
    copy_cay(TREE, TREE2);
    xoa_sach(TREE);
    printf("\ncay 1: "); traverse_NLR(TREE);
    printf("\ncay 2: "); traverse_NLR(TREE2);
 
 
    return 0;
 
    printf("Search for?: "); int x; scanf("%d", &x);
    if (search(TREE, x)){
        printf("FOUND\n");
    } else printf("NOT FOUND\n");
 
}