大话数据结构(5.1)---二叉排序和二叉平衡树_有序列(5,12,30,45,70,73,80,85,89,100,103,109),画出它的二叉判

1. 二叉树排序

二叉排序树(Binary Sort Tree)，又称二叉查找树。它或者是一颗空树。或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上全部节点的值都小于它的根节点的值。
• 若它的右子树不空，则右子树上全部节点的值都大于它的根节点的值；
• 它的左、右子树也分别为二叉排序树。

******************二叉树结构******************
*                              62
*              58                              88
*      47              00              73              99
*  35      51      00      00      00      00      93      00
*00  37  00  00  00  00  00  00  00  00  00  00  00  00  00  00
*********************************************
35,37,47,51,58,62,73,88,93,99
1
2
3
4
5
6
7
8

上面就是一棵二叉排序树，当我们对它进行中序遍历时。就能够得到一个有序的序列{35,37,47,51,58,62,73,88,93,99}.构造一颗二叉排序树，不是为了排序，而是为了提高查找和插入删除关键字的速度。
二叉排序树的操作主要有：

• 查找：递归查找是否存在key；
• 插入：原树中不存在key，插入key返回true，否则返回false；rm
• 删除：

1.1 二叉树查找

比如查找93节点：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-06oguM36-1624528021027)(/Users/user/Library/Application Support/typora-user-images/image-20210624130250914.png)]

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) 
{  
    /*f为叶子节点*/
    /* T为叶子节点待子节点 */
    printf("T = %10p, key = %3d, f = %10p, *p = %10p\n", T, key, f, *p);
    if (!T) /*  查找不成功 当前节点是否为空*/
    { 
        *p = f;    
        return FALSE; 
    } else if (key==T->data) /*  查找成功 */ { 
        *p = T;  
        return TRUE; 
    }  else if (key<T->data) 
        return SearchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */
    else  
        return SearchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.2. 二叉树插入

1.2.1. 插入的节点为根节点

*T = s;         /*  插入s为新的根结点 */
1

1.2.1. 插入的节点为左孩子

p->lchild = s; 
1

1.2.1. 插入的节点为右孩子

 p->rchild = s;
1

/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
/*  插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key) 
{  
    BiTree p,s;
    printf("二叉排序树中插入:key = %d\n", key);
    if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;  
        s->lchild = s->rchild = NULL;  
        if (!p) 
            *T = s;         /*  插入s为新的根结点 */
        else if (key < p->data) 
            p->lchild = s;  /*  插入s为左孩子 */
        else 
            p->rchild = s;  /*  插入s为右孩子 */
        return TRUE;
    } 
    else 
        return FALSE;  /*  树中已有关键字相同的结点，不再插入 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.2. 二叉树删除

/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{ 
    if(!*T) /* 不存在关键字等于key的数据元素 */ 
        return FALSE;
    else
    {
        if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ 
            return Delete(T);
        else if (key<(*T)->data)
            return DeleteBST(&(*T)->lchild,key);
        else
            return DeleteBST(&(*T)->rchild,key);
    }
}

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
Status Delete(BiTree *p)
{
    BiTree q,s;
    /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */
    if((*p)->rchild == NULL) { 
        q  = *p; 
        *p = (*p)->lchild; 
        free(q);
    } else if((*p)->lchild == NULL) {/* 只需重接它的右子树 */
        q  = *p; 
        *p = (*p)->rchild; 
        free(q);
    } else { /* 左右子树均不空 */
        q = *p; 
        s = (*p)->lchild;
        while (s->rchild) { /* 转左，然后向右到尽头（找待删结点的前驱） */
            q = s;
            s = s->rchild;
        }
        /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
        (*p)->data = s->data; 
        if (q! = *p) {
            q->rchild = s->lchild; /*  重接q的右子树 */ 
        } else {
            q->lchild = s->lchild; /*  重接q的左子树 */
        }

        free(s);
    }

    return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

1.2.1. 删除的节点只有一个子树

1. 如图中的58节点，右子树空则只需重接它的左子树（待删结点是叶子也走此分支)
2. 如图中的37节点，只需重接它的右子树

1.2.2. 删除的节点有作业两个节点

删除节点47

1. 方案一
   

2. 方案二
   
   
   

2. 平衡二叉树(AVL树)

2.1 为什么要有平衡二叉树

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树如图 1.1。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。

在此二叉搜索树中查找元素 6 需要查找 6 次。
二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列 A，将其改为图 1.2 的方式存储，查找元素 6 时只需比较 3 次，查找效率提升一倍。

可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。

这种左右子树的高度相差不超过 1 的树为平衡二叉树。

2.2. 定义

平衡二叉查找树：简称平衡二叉树。它具有如下几个性质：

1. 可以是空树。
2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

平衡之意，如天平，即两边的分量大约相同。

2.3. 平衡因子

**定义：**某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。

2.4. 节点结构

定义平衡二叉树的节点结构：

typedef int TElemType;
//TElemType Nil=' '; /* 字符型以空格符为空 */

typedef struct BiTNode  /* 结点结构 */
{
   TElemType data;		/* 结点数据 */
   int bf; /*  结点的平衡因子 */ 
   struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
1
2
3
4
5
6
7
8
9

2.5. AVL树插入时的失衡与调整

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋 与 右旋 。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

2.5.1 左旋

以上图为例，加入新节点 5后， 节点 3 的左子树高度为 1，右子树高度为 3，此时平衡因子为 -2。为保证树的平衡，此时需要对节点 3 做出旋转，因为右子树高度高于左子树，对节点进行左旋操作，流程如下：

/* 对以p为根的二叉排序树作右旋处理， */
/* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
void R_Rotate(BiTree *P)
{ 
	printf("R_Rotate\n");
	BiTree L;
	L=(*P)->lchild; /*  L指向P的左子树根结点 */ 
	(*P)->lchild=L->rchild; /*  L的右子树挂接为P的左子树 */ 
	L->rchild=(*P);
	*P=L; /*  P指向新的根结点 */ 
}
1
2
3
4
5
6
7
8
9
10
11

• 节点的右孩子替代此节点位置
• 右孩子的左子树变为该节点的右子树
• 节点本身变为右孩子的左子树

2.5.2 右旋

右旋操作与左旋类似，操作流程为：

/* 对以P为根的二叉排序树作左旋处理， */
/* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */
void L_Rotate(BiTree *P)
{ 
	printf("L_Rotate\n");
	BiTree R;
	R=(*P)->rchild; /*  R指向P的右子树根结点 */ 
	(*P)->rchild=R->lchild; /* R的左子树挂接为P的右子树 */ 
	R->lchild=(*P);
	*P=R; /*  P指向新的根结点 */ 
}
1
2
3
4
5
6
7
8
9
10
11

• 节点的左孩子代表此节点
• 节点的左孩子的右子树变为节点的左子树
• 将此节点作为左孩子节点的右子树。

2.6. 举例说明

数组为：{3,2,1,4,5,6,7,10,9,8}

******************二叉平衡树结构******************
*              04
*      02              07
*  01      03      06      09
*                05      08  10  
*********************************************
1
2
3
4
5
6

#define LH +1 /*  左高 */ 
#define EH 0  /*  等高 */ 
#define RH -1 /*  右高 */ 
1
2
3

1. 当插入节点2

******************二叉树结构******************
*  3[-1]
*2[0]
*********************************************
1
2
3
4

2. 当插入节点3

******************二叉树结构******************
*    3[2]
*  2[1]
*1[0]
*********************************************
1
2
3
4
5

此时已经失衡，需要进行右旋转

旋转后的结果如下：

******************二叉树结构******************
*     2[0]     
*1[0]     3[0]        
*********************************************
1
2
3
4

3. 当插入节点4

******************二叉树结构******************
*     2[-1]     
*1[0]     3[-1]    
*             4[0]
*********************************************
1
2
3
4
5

4. 当插入节点5

******************二叉树结构******************
*     2[-2]     
*1[0]     3[-2]    
*             4[-1]
*                 5[0]
*********************************************
1
2
3
4
5
6

此时已经失衡，需要进行左旋转

******************二叉树结构******************
*       02[-1]
*  01[0]      04[0]
*          03[0]  05[0]
*********************************************
1
2
3
4
5

5. 当插入节点6

******************二叉树结构******************
*       02[-2]
*  01[0]      04[-1]
*          03[0]  05[-1]
*                     06[0]
*********************************************
1
2
3
4
5
6

此时已经失衡，需要对节点2进行左旋转

******************二叉树结构******************
*         04[0]
*    02[0]      05[-1]
*01[0]  03[0]       06[0]
*********************************************
1
2
3
4
5

6. 当插入节点7

******************二叉树结构******************
*         04[0]
*    02[0]      05[-2]
*01[0]  03[0]       06[-1]
*                       07[0]
*********************************************
1
2
3
4
5
6

此时节点5已经失衡，需要对节点5进行左旋转

******************二叉树结构******************
*           04[0]
*    02[0]        06[-2]
*01[0]  03[0]  05[0] 07[-1]
*                       
*********************************************
1
2
3
4
5
6

7. 当插入节点10

******************二叉树结构******************
*           04[-1]
*    02[0]        06[-1]
*01[0]  03[0]  05[0] 07[-1]
*                       10[0]        
*********************************************
1
2
3
4
5
6

8. 当插入节点9

******************二叉树结构******************
*            04[-2]
*    02[0]         06[-2]
*01[0]  03[0]  05[0]   07[-2]
*                          10[1] 
*                      9[0]        
*********************************************
1
2
3
4
5
6
7

插入10,9时，不是简单的左旋，这时要统一BF。7的BF=-2，10的BF=1，一正一负，符号不统一。先对9,10右旋，再以7为最小不平衡子树左旋

******************二叉树结构******************
*            04[-2]
*    02[0]         06[-2]
*01[0]  03[0]  05[0]     7[-2]
*                            9[-1]        
*                               10[0] 
*********************************************
1
2
3
4
5
6
7

******************二叉树结构******************
*            04[-1]
*    02[0]         06[-1]
*01[0]  03[0]  05[0]     9[0]
*                    7[0]   10[0]        
*********************************************
1
2
3
4
5
6

9. 当插入节点8

******************二叉树结构******************
*            04[-2]
*    02[0]         06[-2]
*01[0]  03[0]  05[0]     9[1]
*                     7[-1]   10[-1] 
*                        8[0]
*********************************************
1
2
3
4
5
6
7

和上面类似

******************二叉平衡树结构******************
*              04
*      02              07
*  01      03      06      09
*                05      08  10  
*********************************************
1
2
3
4
5
6