二叉搜索树BST

 

数据域大小关系:

  根>左,根<右

 

 

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

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

二叉搜索树BST

 

 

  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\n",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\n",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\n",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\n", get_height(tree.root));
116     
117     printf("max = %d\n", get_maximum(tree.root)); 
118     
119 }

 

 

上一篇:二叉搜索树


下一篇:面试总结 | 百度 NLP 实习生