二叉搜索树(BST)

数据域大小关系：

　　根>左，根<右

假设所有二叉树的所有结点数据都是正数，且两两不同

arr 6,3,8,2,5,1,7

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct node{
  5     int data;
  6     struct node* left;
  7     struct node* right;
  8 } Node;
  9 
 10 typedef struct{
 11     Node* root;
 12 } Tree;
 13 
 14 void insert(Tree* tree, int value)
 15 {
 16     Node* node= malloc(sizeof(Node));
 17     node -> data  = value;
 18     node -> left  = NULL;
 19     node -> right = NULL;
 20     
 21     if(tree -> root == NULL){
 22         tree -> root = node;
 23         return ;
 24     }
 25     else
 26     {
 27         Node* temp = tree -> root;
 28         while(temp != NULL){
 29             if(temp -> data > value){
 30                 //走左边有两种情况 
 31                 if(temp -> left == NULL){
 32                     temp -> left = node;
 33                     return;
 34                 }
 35                 else
 36                     temp = temp -> left;
 37             }
 38             if(temp -> data < value){
 39                 if(temp -> right == NULL){
 40                     temp -> right = node;
 41                     return;
 42                 }
 43                 else
 44                     temp = temp -> right;
 45             }
 46         }
 47     }
 48 }
 49 int get_height(Node* node)//为了便于递归的进行 
 50 {
 51     if(node == NULL)
 52         return 0;
 53     else
 54     {
 55         int h_left  = get_height(node -> left);
 56         int h_right = get_height(node -> right);
 57         int max = h_left;
 58         if(max < h_right){
 59             max = h_right;
 60         }
 61         return max + 1;
 62     }
 63 }
 64 int get_maximum(Node* node)
 65 {
 66     if(node == NULL)
 67         return -1;//所有节点全为正数时 
 68     else{
 69         int m1 = get_maximum(node -> left);
 70         int m2 = get_maximum(node -> right);
 71         int m3 = node -> data;
 72         int max = m1;
 73         if(m2>max) {
 74             max = m2;
 75         }
 76         if(m3>max){
 77             max = m3;
 78         }
 79         return max;
 80     } 
 81 }
 82 
 83 void preorder(Node* node){
 84     if(node != NULL){
 85         printf("%d
",node -> data);
 86         preorder(node -> left);
 87         preorder(node -> right);
 88     }
 89 }
 90 void inorder(Node* node){
 91     if(node != NULL){
 92         inorder(node -> left);
 93         printf("%d
",node -> data);
 94         inorder(node -> right);
 95     }
 96 }
 97 void postorder(Node* node){
 98     if(node != NULL){
 99         postorder(node -> left);
100         postorder(node -> right);
101         printf("%d
",node -> data);
102     }
103 }
104 
105 int main(){
106     Tree tree;
107     tree.root=NULL;
108     
109     int arr[7]={6,3,8,2,5,1,7};
110     
111     int i;
112     for(i=0; i<7; i++)
113         insert(&tree, arr[i]);
114         
115     printf("h = %d
", get_height(tree.root));
116     
117     printf("max = %d
", get_maximum(tree.root)); 
118     
119 }

//----------------------------------

新增问题：

1）复制二叉树

刚拿到手时候，直接传指针，输不出来值。检查一番，发现犯了低级错误：直接传递指针变量，因为此时传递的是指针变量的指向，相当于实体变量。

Node* Copy(Node* ExtN,Node* newN){
    //复制二叉树，中序方法 
    if(ExtN == NULL){
        return NULL;
    }
    else
    {
        newN = (Node*)malloc(sizeof(Node));
        newN -> data = ExtN -> data;
        newN -> left  = Copy(ExtN -> left, newN -> left);
        newN -> right = Copy(ExtN -> right,newN -> right);
        return newN;
    }
} 

...

int main(){
    //...

    Tree newT;
    newT.root=Copy(tree.root, newT.root);
    preorder(newT.root);
    //复制二叉树

    //...      
    

}

2）计算结点个数

 1 int Count(Node *node){
 2     //统计节点总数 
 3     if(node == NULL){
 4         return 0;
 5     }
 6     else{
 7         return Count(node -> left)+
 8                Count(node -> right)+1;
 9     }
10 }

3）统计叶子个数

 1 int countLeaf(Node *node){
 2     //统计叶子结点的个数 
 3     if(node == NULL)
 4         return 0;
 5     if(node -> left == NULL && node -> right == NULL)
 6         return 1;
 7     else{
 8         return countLeaf(node -> left) + countLeaf(node -> right);
 9     } 
10 }