#3.二叉查找树

2017-06-09

要求：

给定一个（无序）数组，创建一棵基本的二叉查找树。

考虑：

1 . 什么是二叉查找树
2 . 空数组

知识点：

1 . 二叉查找树： 在数值上： 左孩子<根<右孩子。
2 . 中序遍历： 先访问左子树，再访问根节点，最后访问右子树。对于每棵子树，也采用此顺序访问。中序遍历一棵二叉查找树，就能得到一个非递减的数列。

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
// add node to a binary tree with root
add_node(root){
for each element in ary:   
    if root is null:
        make it the root node
    else:
        if ele's val > root:
            add_node(root->right)
        else if ele's val < root:
            add_node(root->left)
        else: // not create a new node
            root's num ++
}

代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
* Prob: Construct a binary seach tree
* Idea: left < root < right, mid order traverse.
* Time: O(nlogn)
* Space:O(n)
* Mistakes: The tree's root is nullptr, so the output is null.
* 2017-06-06
*/
#include<bits/stdc++.h>
using namespace std;
typedef struct BinaryTreeNode{
    int value;  // node value
    int num;    // num of nodes with the same value
    BinaryTreeNode *right;
    BinaryTreeNode *left;
}BTNode;
struct Ancestor{
    BTNode *node;
    BTNode *parent;
    bool is_left_child;
};
Ancestor *des_node = nullptr;
// add a node to binary tree
BTNode* add_node(BTNode *root, int val){
    BTNode *ptr = root;
    if(!ptr){ // ptr is null
        ptr = new BTNode;
        ptr->value = val;
        ptr->num = 1;
        ptr->left = ptr->right = nullptr;
    }else{
        if(val > ptr->value){
            ptr->right = add_node(ptr->right, val);
        }else if(val < ptr->value){
            ptr->left = add_node(ptr->left, val);
        }else{
            ptr->num += 1;
        }
    }
    return ptr;
}
// build a binary tree
BTNode* build_binary_tree(int* ary, int node_num){
    BTNode *root = nullptr;
    if(node_num<=0) return nullptr;
    root = add_node(root, ary[0]);
    for(int i=1; i<node_num; i++){
        add_node(root, ary[i]);
    }
    return root;
}
// print binary tree
void output_binary_tree(BTNode *root){
    if(!root) return;
    BTNode* ptr = root;
    if(ptr->left){
        output_binary_tree(ptr->left);
    }
    cout<<ptr->value<<":"<<ptr->num<<"  ";
    if(ptr->right){
        output_binary_tree(ptr->right);
    }
}
// main func
int main(){
    int ary[] = {90,12,33,-100,20, 23,12,34,22,78, -1,88,27,9,8, 90,90,33,10,24, 67,54,24,89,120, 44,55,34,100,1};
    int node_num = sizeof(ary)/sizeof(ary[0]);
    cout<<"Node num:"<<node_num<<endl;
    // build tree
    BTNode *root = build_binary_tree(ary, node_num);
    cout<<"\nThe Binary Tree is:"<<endl;
    output_binary_tree(root);
    cout<<endl;
    return 0;
}