读书笔记: 二叉树 Bintree

1
2
3
4
5

typedef struct tree_node *tree_pointer;
typedef struct tree_node{
    int data;
    tree_pointer left_child,right_child;
}tree_node;

Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//递归查找
tree_pointer search(tree_pointer root,int key){
    if (!root) return NULL;
    if (key == root->data) return root;
    if (key < root->data)
        return search(root->left_child, key);
    return search(root->right_child, key);
}

//迭代查找
tree_pointer iteration_search(tree_pointer tree,int key){
    while(tree){
        if(tree->data == key) return tree;
        if(key < tree->data)
            tree=tree->left_child;
        else
            tree=tree->right_child;
    }
    return NULL;
}

Insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

//修改以适应 insert_node,如果树为空或已找到节点，返回null。否则，返回指向查找过程中遇到树中最后一个节点的指针。
tree_pointer modified_search(tree_pointer tree,int key){
    if(!tree) return NULL;

    while(tree){
        if(tree->data == key) return NULL;
        if(key < tree->data) {
            if(tree->left_child) break;
            tree=tree->left_child;
        }else{
            if(tree->right_child) break;
            tree=tree->right_child;
        }
    }
    return tree;
}

void insert_node(tree_pointer *node,int num){
    // if num is in the tree pointed at by node do nothing;
    tree_pointer ptr,temp=modified_search(*node, num);
    if(temp || !(*node)){
        ptr = (tree_pointer) malloc (sizeof(tree_node));
        if(!ptr){
            fprintf(stderr, "full");
            exit(1);
        }
        ptr->data=num;
        ptr->left_child=ptr->right_child=NULL;
        if(*node){
            if(num < temp->data) temp->left_child = ptr;
            else temp->right_child = ptr;
        } else {
            *node = ptr;
        }
    }

}