二叉查找树（Binary Search Tree）

深碍√TFBOYSˉ_ 2021-12-20 06:29 273阅读 0赞

### Date：2019-06-25 14:40:32 ###

### 基本操作 ###

*  注意：数据量较大时，插入建树的时间复杂度会很高，慎用！

1 //查找
     2 void Search(node *root, int x)
     3 {
     4     if(root == NULL)
     5     {
     6         printf("search failed\n");
     7         return;
     8     }
     9     if(x == root->data)
    10         printf("%d\n", root->data);
    11     else if(x < root->data)
    12         Search(root->lchild, x);
    13     else if(x > root->data)
    14         Search(root->data)
    15         Search(root->rchild, x);
    16 }
    17 
    18 //插入
    19 void Insert(node *root, int x)
    20 {
    21     if(root == NULL)
    22     {
    23         root = newNode(x);  //新建结点
    24         return;
    25     }
    26     if(x == root->data)
    27         return;
    28     else if(x > root->data)
    29         Insert(root->rchild, x);
    30     else if(x < root->data)
    31         Insert(root->lchild, x);
    32 }
    33 
    34 //建立
    35 node* Create(int data[], int n)
    36 {
    37     node *root = NULL;
    38     for(int i=0; i<n; i++)
    39         Insert(root, data[i]);
    40 
    41     return root;
    42 }
    43 
    44 //删除
    45 
    46 //寻找前驱
    47 node* FindMax(node *root)
    48 {
    49     while(root->rchild != NULL)
    50         root = root->rchild;
    51     return root;
    52 }
    53 
    54 //寻找后继
    55 node* FindMin(node *root)
    56 {
    57     while(root->lchild != NULL)
    58         root = root->lchild;
    59     return root;
    60 }
    61 
    62 //删除结点root
    63 void Delete(node *&root, int x)
    64 {
    65     if(root == NULL)
    66         return;
    67     if(root->data == x)
    68     {
    69         if(root->lchild==NULL & root->rchild==NULL) //叶子结点直接删除即可
    70             root = NULL;
    71         else if(root->lchild != NULL)
    72         {
    73             node *pre = FindMax(root->lchild);      //寻找左子树的最大值（最右结点）
    74             root->data = pre->data;                 //与被删除结点替换
    75             Delete(root->lchild, pre->data);        //删除替换后的结点
    76         }
    77         else if(root->rchild != NULL)
    78         {
    79             node *pre = FindMin(root->rchild);      //寻找右子树的最小值（最左结点）
    80             root->data = pre->data;
    81             Delete(root->rchild, pre->data);
    82         }
    83     }
    84     else if(x < root->data)
    85         Delete(root->lchild, x);
    86     else if(x > root->data)
    87         Delete(root->rchild, x);
    88 }

### 删除优化 ###

*  删除操作中，找到替换结点后，该结点就是接下来需要删除的结点，直接删除即可
 *  目前PAT考试中还没有考察过删除结点相关的算法

1 #include<stdio.h>
      2 const int M = 10;
      3 const int data[M] = {
        6,12,18,4,5,7,16,19,17,9};
      4 
      5 struct node
      6 {
      7     int data;
      8     node *lchild, *rchild;
      9 };
     10 
     11 node* FindMax(node *root)
     12 {
     13     while(root->rchild->rchild)
     14         root = root->rchild;
     15     return root;
     16 }
     17 
     18 node *FindMin(node *root)
     19 {
     20     while(root->lchild->lchild)
     21         root = root->lchild;
     22     return root;
     23 }
     24 
     25 void BST(node *&root, int x)
     26 {
     27     if(!root)
     28     {
     29         root = new node;
     30         root->data = x;
     31         root->lchild = NULL;
     32         root->rchild = NULL;
     33         return;
     34     }
     35     if(x == root->data)
     36     {
     37         if(!root->lchild && !root->rchild)
     38             root = NULL;
     39         else if(root->lchild)
     40         {
     41             node *pre;
     42             if(root->lchild->rchild == NULL)
     43             {
     44                 pre = root->lchild;
     45                 root->lchild = pre->lchild;
     46             }
     47             else
     48             {
     49                 node *fa = FindMax(root->lchild);
     50                 pre = fa->rchild;
     51                 fa->rchild = pre->lchild;
     52             }
     53             root->data = pre->data;
     54             delete(pre);
     55         }
     56         else if(root->rchild)
     57         {
     58             node *pre;
     59             if(root->rchild->lchild == NULL)
     60             {
     61                 pre = root->rchild;
     62                 root->rchild = pre->rchild;
     63             }
     64             else
     65             {
     66                 node *fa = FindMin(root->rchild);
     67                 pre = fa->rchild;
     68                 fa->rchild = pre->lchild;
     69             }
     70             root->data = pre->data;
     71             delete(pre);
     72         }
     73     }
     74     else if(x < root->data)
     75         BST(root->lchild, x);
     76     else if(x > root->data)
     77         BST(root->rchild, x);
     78 }
     79 
     80 void Traverse(node *root)
     81 {
     82     if(root == NULL)
     83         return;
     84     Traverse(root->lchild);
     85     printf("%d ", root->data);
     86     Traverse(root->rchild);
     87 }
     88 
     89 node* Create()
     90 {
     91     node *root = NULL;
     92     for(int i=0; i<M; i++)
     93         BST(root, data[i]);
     94 
     95     return root;
     96 }
     97 
     98 int main()
     99 {
    100 #ifdef ONLINE_JUDGE
    101 #else
    102     freopen("Test.txt", "r", stdin);
    103 #endif // ONLINE_JUDGE
    104 
    105     node *root = Create();
    106     Traverse(root);
    107     printf("\n");
    108     BST(root, 6);
    109     Traverse(root);
    110 
    111     return 0;
    112 }

转载于:https://www.cnblogs.com/blue-lin/p/11082782.html