期末复习（二）_在初始为空的平衡二叉树中依次插入33、88、66、22、11、15、44、40,画出平衡二叉

期末复习（二）

数据结构

二叉排序树（二叉查找树）

特性：

1. 若左子树不空，左子树上的所有节点的值均小于根节点的值；
2. 若右子树不空，右子树上的所有节点的值均大于于根节点的值；
3. 左子树和右子树也是二叉排序树

插入

当树中不存在查找的节点时，做插入操作，插入操作较简单，只需要在查找不成功时，访问的最后一个节点插入即可，若插入值更大，则是最后一个节点的右孩子，否则是左孩子。

例子：
在初始为空的二叉排序树中依次插入56，64，92，80，88，75

代码实现：

bool SearchBST(BiNode* tree, int key, BiNode* f, BiNode*& p)
{
    if (!tree)
    {
        p = f;                  // 查找不成功，指针指向最后访问的非空节点
        return false;
    }
    else if (key == tree->data)
    {
        p = tree;           // 查找成功，指针指向当前节点
        return true;
    }
    else if (key < tree->data)
    {
        SearchBST(tree->lchild, key, tree, p);      //查找值比当前节点数据大，继续在左子树中查找
    }
    else
    {
        SearchBST(tree->rchild, key, tree, p);     //查找值比当前节点数据小，继续在右子树中查找
    }
}
void InsertBST(BiNode*& tree, int e)
{
    BiNode* p = tree;
    if (!SearchBST(tree, e, NULL, p))        //没有查找到，需要插入
    {
        BiNode *s = new BiNode();
        s->data = e;
        s->lchild = NULL;
        s->rchild = NULL;            //插入的节点是叶子节点
        if (!p)
        {
            tree = s;                  // 树现在是空树，插入节点变为根节点
        }
        else if (e < p->data)
        {
            p->lchild = s;           //插入值比最后访问的节点的数据小，作为左孩子插入
        }
        else
        {
            p->rchild = s;
        }
        return;
    }
    return;
}

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

删除

被删除的节点有三种情况：①叶子节点； ②只有左子树或右子树； ③同时有左、右子树

①叶子节点，直接删除节点

② 只有左子树（右子树），左子树（右子树）整颗直接占据它父节点的位置

③ 同时有左、右子树，

先用指针指向左孩子，然后一直找右孩子，直到没有右孩子，便把当前节点的值，取代被删的节点， 并且删除掉当前节点（叶子节点或只有左子树）

代码实现：

void Delete(BiNode*& tree)
{
    if (tree->lchild == NULL && tree->rchild == NULL)    //只有叶子节点
    {
        tree = NULL;
    }
    else if (tree->lchild == NULL)                    //只有右子树
    {
        BiNode* temp = tree;
        tree = tree->rchild;
        delete temp;
    }
    else if (tree->rchild == NULL)            //只有左子树
    {
        BiNode* temp = tree;
        tree = tree->lchild;
        delete temp;
    }
    else                         //既有左子树，又有右子树
    {
        BiNode* temp = tree, * s = tree->lchild;     //指针指向要删除的节点的左孩子，定义的temp变量是为了防止左孩子没有右孩子可找时，需要重接左子树，而不是重接右子树
        while (s->rchild)
        {
            temp = s;
            s = s->rchild;          
        }         //找最大右孩子，即比删除节点值小，但最接近的值，可以继续保持二叉排序树的性质
        tree->data = s->data;
        if (temp != tree)
        {
            temp->rchild = s->lchild;
        }
        else
        {
            temp->lchild = s->lchild;
        }
        delete s;
    }
}

void DeleteBST(BiNode*& tree, int key)
{
    if (tree == NULL)
    {
        return;
    }
    else
    {
        if (key == tree->data)
        {
            Delete(tree);    //找到要删除的节点
            return;
        }
        else if (key < tree->data)
        {
            DeleteBST(tree->lchild, key);   //向左子树继续找要删除的节点
            return;
        }
        else
        {
            DeleteBST(tree->rchild, key);     //向右子树继续找要删除的节点
            return;
        }
    }
}

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

以下部分只有理论知识（个人复习练习）

平衡二叉树

平衡二叉树，又称AVL树，是二叉排序树的特殊形式，树中每个结点的左、右子树深度之差的绝对值不大于1，即|hL-hR|≤1

插入：（删除类似）

练习：在空平衡二叉树中依次插入33、88、66、22、11、15、44、40（个人练习）

删除节点11、88

参考资料：sztu数据结构课件