数据结构【查找】—二叉树排序以及查找

àì夳堔傛蜴生んèń 2022-10-02 15:55 186阅读 0赞

讲解：

**总结一句话：**

小的左边，大的放右边。

**特点：**

二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二又排序树。

![1463063-20190324160411232-808620531.png][]

二叉树创建代码：

1 //创建二叉树
     2 void InsertBST(BiTree* &T, int elem) {
     3     BiTree *p = new  BiTree;
     4     p->data = elem;
     5     p->lchild = NULL;
     6     p->rchild = NULL;
     7     if (!T) {
     8         T = p;//为空树        
     9         return;
    10     }
    11 
    12     if (T->data == elem)
    13         return;//此数已经存在
    14 
    15     while (true) {
    16         if (elem > T->data) {
    17             if (T->rchild != NULL)
    18                 T = T->rchild;//走到最右端
    19             else {
    20                 T->rchild = p;//添加为右子树
    21                 return;
    22             }
    23         }
    24         else {
    25             if (T->lchild != NULL)
    26                 T = T->lchild;//走到最左端
    27             else {
    28                 T->lchild = p;//添加为左子树
    29                 return;
    30             }
    31         }
    32     }
    33 
    34 }

二叉树排序：

通过二叉树的中序遍历，得到的就是一个有序数组

代码：

1 void ShowTree(BiTree *T) {
    2     //进行中序浏览
    3     if (T) {
    4         ShowTree(T->lchild);
    5         cout << T->data << "—>";
    6         ShowTree(T->rchild);
    7     }
    8 }

二叉树查找：

使用递归，通过比较大小来找到左子树或右子树。

![1463063-20190324160716426-358877850.png][]

二叉树查找代码：*　　*

1 //对二叉树进行查找工作
    2 int SearchData(BiTree *T, int num) {
    3     if (!T)return 0;
    4     if (T->data == num)return 1;
    5     if (num > T->data)SearchData(T->rchild,num);
    6     else SearchData(T->lchild, num);
    7 }

二叉树的删除是重点也是难点：

当要删除节点位于右端末，即无右子树，则用它的左子树接替他的位置；

![1463063-20190324161221332-1922327002.png][]

当要删除节点位于左端末，即无左子树，则用它的右子树接替他的位置；

![1463063-20190324161336043-333377255.png][]

当要删除节点位于中间，即既有左子树，又有右子树，用左子树的最大数代替，即左子树的最右端末。

![1463063-20190324161614440-996736554.png][]

删除代码：

1 //进行删除
     2 //重点，也是难点
     3 int Delete(BiTree* &T) {
     4     BiTree *p, *q;
     5     if (T->rchild == NULL) {
        //若该结点没有右子树，则将该节点的左子树代替其，并删除
     6         p = T;
     7         T = T->lchild;
     8         delete(p);
     9     }
    10     else if (T->lchild == NULL) {
        //若该结点没有左子树，则将该节点的右子树代替其，并删除
    11         p = T;
    12         T = T->rchild;
    13         delete(p);
    14     }
    15     else {
        //左右子树都存在
    16         p = T;
    17         q = T->lchild;
    18         while (q->rchild) {
        //走到T左支的末端，此时他是左边最大的数
    19             p = q;//记住前端点
    20             q = q->rchild;
    21         }
    22         T->data = q->data;//前驱的数字用最右端数字代替
    23         if (p != T)//将末端的左孩子连接，因为此时他是左端最大的数字
    24             p->rchild = q->lchild;
    25         else
    26             p->lchild = q->lchild;//重接左子树
    27         delete(q);//释放左端最大值
    28     }
    29     return 1;
    30 }
    31 
    32 
    33 //对二叉树进行删除操作
    34 int DeleteBST(BiTree* &T, int num) {
    35     if (!T)return false;
    36     if (num == T->data) {
    37         Delete(T);
    38         return true;
    39     }
    40     else if (num > T->data)DeleteBST(T->rchild, num);
    41     DeleteBST(T->lchild, num);
    42 }

完整代码：

1 #include "000库函数.h"
      2 
      3 #define MAXSIZE 100
      4 
      5 
      6 //二叉树的结构
      7 struct BiTree
      8 {
      9     int data;
     10     BiTree *lchild, *rchild;
     11 };
     12 
     13 //创建二叉树
     14 void InsertBST(BiTree* &T, int elem) {
     15     BiTree *p = new  BiTree;
     16     p->data = elem;
     17     p->lchild = NULL;
     18     p->rchild = NULL;
     19     if (!T) {
     20         T = p;//为空树        
     21         return;
     22     }
     23 
     24     if (T->data == elem)
     25         return;//此数已经存在
     26 
     27     while (true) {
     28         if (elem > T->data) {
     29             if (T->rchild != NULL)
     30                 T = T->rchild;//走到最右端
     31             else {
     32                 T->rchild = p;//添加为右子树
     33                 return;
     34             }
     35         }
     36         else {
     37             if (T->lchild != NULL)
     38                 T = T->lchild;//走到最左端
     39             else {
     40                 T->lchild = p;//添加为左子树
     41                 return;
     42             }
     43         }
     44     }
     45 
     46 }
     47 
     48 void ShowTree(BiTree *T) {
     49     //进行中序浏览
     50     if (T) {
     51         ShowTree(T->lchild);
     52         cout << T->data << "—>";
     53         ShowTree(T->rchild);
     54     }
     55 }
     56 
     57 //对二叉树进行查找工作
     58 int SearchData(BiTree *T, int num) {
     59     if (!T)return 0;
     60     if (T->data == num)return 1;
     61     if (num > T->data)SearchData(T->rchild,num);
     62     else SearchData(T->lchild, num);
     63 }
     64 
     65 
     66 //进行删除
     67 //重点，也是难点
     68 int Delete(BiTree* &T) {
     69     BiTree *p, *q;
     70     if (T->rchild == NULL) {
        //若该结点没有右子树，则将该节点的左子树代替其，并删除
     71         p = T;
     72         T = T->lchild;
     73         delete(p);
     74     }
     75     else if (T->lchild == NULL) {
        //若该结点没有左子树，则将该节点的右子树代替其，并删除
     76         p = T;
     77         T = T->rchild;
     78         delete(p);
     79     }
     80     else {
        //左右子树都存在
     81         p = T;
     82         q = T->lchild;
     83         while (q->rchild) {
        //走到T左支的末端，此时他是左边最大的数
     84             p = q;//记住前端点
     85             q = q->rchild;
     86         }
     87         T->data = q->data;//前驱的数字用最右端数字代替
     88         if (p != T)//将末端的左孩子连接，因为此时他是左端最大的数字
     89             p->rchild = q->lchild;
     90         else
     91             p->lchild = q->lchild;//重接左子树
     92         delete(q);//释放左端最大值
     93     }
     94     return 1;
     95 }
     96 
     97 
     98 //对二叉树进行删除操作
     99 int DeleteBST(BiTree* &T, int num) {
    100     if (!T)return false;
    101     if (num == T->data) {
    102         Delete(T);
    103         return true;
    104     }
    105     else if (num > T->data)DeleteBST(T->rchild, num);
    106     DeleteBST(T->lchild, num);
    107 }
    108 
    109 int T032(void)
    110 {
    111     int i;
    112     int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
    113     BiTree *T = new BiTree;
    114     T = NULL;
    115     BiTree *p;
    116     for (i = 0; i < 10; i++) {
    117         InsertBST(T, a[i]);
    118         if (i == 0)
    119             p = T;//记住头结点的位置
    120         T = p;//仍然返回头结点，从头结点开始重新遍历
    121     }
    122     ShowTree(T);
    123     cout << endl;
    124     cout << "找到没？" << endl << SearchData(T, 99) << endl;
    125     p = T;//记住头结点
    126     DeleteBST(T, 93);
    127     T = p;
    128     ShowTree(T);
    129     cout << endl;
    130     p = T;//记住头结点
    131     DeleteBST(T, 37);
    132     T = p;
    133     ShowTree(T);
    134     cout << endl;
    135     return 0;
    136 }

转载于:https://www.cnblogs.com/zzw1024/p/10588656.html

[1463063-20190324160411232-808620531.png]: /images/20220109/9f96a581da7c47abb6ad753af7e8c377.png
[1463063-20190324160716426-358877850.png]: /images/20220109/97df2820a6fe481d8afd3119f5e72434.png
[1463063-20190324161221332-1922327002.png]: /images/20220109/5adcb8f243904a698f143b5381ef0dd3.png
[1463063-20190324161336043-333377255.png]: /images/20220109/9a68faf3e6fc4ae2a57b9169c5a3df09.png
[1463063-20190324161614440-996736554.png]: /images/20220109/456ab528895c42da886bd366d4cabe8b.png