Tree 구현

typedef int BData;
 
typedef struct _bTreeNode{
    BData item;
    struct _bTreeNode *left_child;
    struct _bTreeNode *right_child;
}BTreeNode;
 
int main(){
    BTreeNode *n1 = (BTreeNode*)malloc(sizeof(BTreeNode));
    BTreeNode *n2 = (BTreeNode*)malloc(sizeof(BTreeNode));
    BTreeNode *n3 = (BTreeNode*)malloc(sizeof(BTreeNode));
    
    n1->item = 10;
    n1->left_child = n2;
    n1->right_child = NULL;
 
    n2->item = 20;
    n2->left_child = n3;
    n2->right_child = NULL;
 
    n3->item = 30;
    n3->left_child = NULL;
    n3->right_child = NULL;
    
    free(n1),free(n2),free(n3);
    return 0;
}

---

typedef int BData;
 
typedef struct _bTreeNode{
    BData item;
    struct _bTreeNode *left_child;
    struct _bTreeNode *right_child;
}BTreeNode;
 
BTreeNode* CreateNode(BData item){
    BTreeNode* node= (BTreeNode*)malloc(sizeof(BTreeNode));
    node->item = item;
    node->left_child = NULL;
    node->right_child = NULL;
 
    return node;
}
 
void DestoryNode(BTreeNode* node){
    free(node);
}
 
void CreateLeftSubtree(BTreeNode* root, BTreeNode* left){
    if(root->left_child !=NULL)
        exit(1);
    
    root->left_child = left;
}
 
void CreateRightSubtree(BTreeNode* root, BTreeNode* right){
    if(root->right_child != NULL)
        exit(1);
 
    root->right_child = right;
}
 
void Inorder(BTreeNode* root);
void Preorder(BTreeNode* root);
void Postorder(BTreeNode* root);
void Levelorder(BTreeNode* root);
 
int main(){
    BTreeNode* node1 = CreateNode(1);
    BTreeNode* node2 = CreateNode(2);
    BTreeNode* node3 = CreateNode(3);
    BTreeNode* node4 = CreateNode(4);
    BTreeNode* node5 = CreateNode(5);
    BTreeNode* node6 = CreateNode(6);
    
    CreateLeftSubtree(node1,node2);
    CreateRightSubtree(node1,node3);
 
    CreateLeftSubtree(node2,node4);
    CreateRightSubtree(node2,node5);
 
    CreateLeftSubtree(node3,node6);
    
    DestoryNode(node1);
    DestoryNode(node2);
    DestoryNode(node3);
    DestoryNode(node4);
    DestoryNode(node5);
    DestoryNode(node6);
    
    return 0;
}

---

 
int Node(BTreeNode * node){
    int r= 0, l = 0;
 
    if(node->right_child != NULL){
        r = Node(node->right_child);
    }
    if(node->left_child != NULL){
        l = Node(node->left_child);
    }
    return 1+r+l;
}
 
int Height(BTreeNode * node){
    int r= 0, l = 0;
 
    if(node->right_child != NULL){
        r = Height(node->right_child);
    }
    if(node->left_child != NULL){
        l = Height(node->left_child);
    }
    return 1+max(r,l);
}

---

Property of Binary Tree

 

The height of Binary Tree is k.

-> Minimum # of nodes = k.

-> Maximum # of nodes = 2^k - 1

 

The # of nodes in a tree is n.

-> Minimum height = ceiling| lg(n+1) |

-> Maximum height = n

 

Rule of Array representation.

- parent node = floor| (i-1)/2 |

- left child = 2(i+1) - 1

- right child = 2(i+1)