二叉查找树

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef struct SortTree
  4 {
  5     int data;
  6     struct SortTree* left;
  7     struct SortTree* right;
  8 }Node;
  9 Node* root;
 10 void Init(int key)
 11 {
 12     root=(Node*)malloc(sizeof(Node));  //向系统申明指针 
 13     root->data=key;
 14     root->left=NULL;
 15     root->right=NULL;
 16 }
 17 void insert(int key) 
 18 {
 19     Node* t=root;
 20     Node* pre=NULL;
 21     while (t!=NULL)
 22     {
 23         pre=t;
 24         if (key<t->data) t=t->left;
 25         else if (key>t->data) t=t->right;
 26         else return;  //若节点已经存在 则直接返回 
 27     }
 28     if (key<pre->data)
 29     {
 30         pre->left=(Node*)malloc(sizeof(Node)),pre->left->data=key;
 31         pre->left->left=NULL,pre->left->right=NULL;
 32     }
 33     else 
 34     {
 35         pre->right=(Node*)malloc(sizeof(Node)),pre->right->data=key;
 36         pre->right->left=NULL,pre->right->right=NULL;
 37     }
 38 }
 39 bool search(Node* root,int key)  //查找是否存在节点 
 40 {
 41     while (root!=NULL)
 42     {
 43         if (key==root->data) return true;
 44         else if (key<root->data) root=root->left;
 45         else root = root->right;
 46     }
 47     return false;
 48 }
 49 int delete_node(Node* node,int key)
 50 {
 51     if (node==NULL) return  -1;
 52     else
 53     {
 54         if (node->data==key)  //若找到删除节点 
 55         {
 56             Node* temp=pre_node(root,node,key);
 57             Node* t=NULL;
 58             if (node->right=NULL)    //若其右子树为空 
 59             {
 60                 temp=node;
 61                 node=node->left;
 62                 if (temp->left->data==t->data)
 63                 {
 64                     Node* free_node=t;
 65                     temp->left=node;
 66                     free(free_node);
 67                     free_node=NULL;
 68                 }
 69                 else 
 70                 {
 71                     Node* free_node=t;
 72                     temp->right=node;
 73                     free(free_node);
 74                     free_node=NULL;
 75                 }
 76             }
 77             else if (node->left==NULL)  //若其左子树为空 
 78             {
 79                 t=node;
 80                 node=node->right;
 81                 if (temp->left->data==t->data)
 82                 {
 83                     Node* free_node=t;
 84                     temp->left=node;
 85                     free(free_node);
 86                     free_node=NULL;
 87                 }
 88                 else 
 89                 {
 90                     Node* free_node=t;
 91                     t->right=node;
 92                     free(free_node);
 93                     free_node=NULL;
 94                 }
 95             }
 96             else  //若左右子树都存在，则选择左子树最大节点为节点 保证其右子树为空 
 97             {
 98                 t=node;
 99                 Node* left_max=node->left;
100                 while (left_max->right!=NULL)
101                 {
102                     t=left_max;
103                     left_max=left_max->right;
104                 }
105                 node->data=left_max->data; //已经替换数值 所以后面不需要交换指针 
106                 if (t!=node)
107                 {
108                     t->right=left_max->left;
109                     free(left_max);
110                     left_max=NULL; 
111                 }
112                 else 
113                 {
114                     t->left=left_max->left;   //相当于放一个空 
115                     free(left_max);
116                     left_max=NULL;
117                 }
118             }
119         }
120         else if (key<node->data) delete_node(node->left,key);  //接着找到目标删除节点 
121         else if (key>node->data) delete_node(node->right,key);
122     }
123 }
124 Node* pre_node(Node* root,Node* node,int key)  //找到 节点上一个父节点 
125 {
126     if (root==NULL||node==root) return node;  //特判一下根节点情况 
127     else
128     {
129         if (root->left!=NULL&&root->left->data==key) return root;
130         else if (root->right!=NULL&&root->right->data==key) return root;
131         else if (key<root->data) return pre_node(root->left,node,key);
132         else return pre_node(root->right,node,key);
133     }
134 }
135 int main ()
136 {
137     
138 }