数据结构——二叉排序树

欢迎大家来到IT世界,在知识的湖畔探索吧!

二叉排序树的概念

二叉排序树（Binary Sort Tree），又称为二叉查找树，是一种结点值之间具有一定数量级次序的二叉树，具有以下性质：

• 若其左子树存在，则其左子树中每个结点的值都不大于该结点的值。
• 若其右子树存在，则其右子树中每个结点的值都不小于该结点的值。
• 若其左右子树都存在，则分别为二叉排序树。

如图1是一棵二叉排序树：

图1 二叉排序树

欢迎大家来到IT世界,在知识的湖畔探索吧!

从二叉排序树结构中可以看出，查询每个结点需要的比较次数为结点高度加1。查找结点值“3”，需要比较两次；查找结点值“0“，需要比较四次。因此整棵树的高度越低，结点的查询复杂度越低。

二叉排序的极端情况

• 二叉排序树是一棵完全二叉树，如图1就是完全二叉树，其查找复杂度为。
• 二叉排序树的每一层只有一个结点，如图：

图2 单结点的二叉排序树

此时二叉排序树退化成链表查询，查询复杂度为。

二叉排序树的插入

【算法步骤】

• 若二叉排序树为空，则创建新结点作为根结点，根结点值为key。
• 若二叉排序树非空，则需要将key与根结点值比较：

a. 若key等于Tree->data，则无需操作。

b. 若key小于Tree->data，则将key插入左子树。

c. 若key大于Tree->data，则将key插入右子树。

【算法代码】

BiTree BSTInsert(BiTree& Tree, ElemType key) { if (nullptr == Tree) /*空树或者遍历到叶子结点*/ { Tree = (BiTNode*)malloc(sizeof(BiTNode)); Tree->data = key; Tree->lchild = nullptr; Tree->rchild = nullptr; } else if (Tree->data > key)/*如果key小于当前结点的值，则插入左结点*/ { Tree->lchild = BSTInsert(Tree->lchild, key); } else if (Tree->data < key)/*如果key大于当前结点的值，则插入右结点*/ { Tree->rchild = BSTInsert(Tree->rchild, key); } return Tree; }

欢迎大家来到IT世界,在知识的湖畔探索吧!

例如，假设原二叉排序树为空树，对一组数据 {3，5，7，2，1} 做查找以及插入操作时，可以构建出一个含有表中所有关键字的二叉排序树，过程如图3所示:

图3 二叉排序树插入过程

二叉排序树的查找

【算法步骤】

• 若二叉排序树为空，返回空指针。
• 若key等于Tree->data，则查找成功，返回结点地址。
• 若key小于Tree->data，则递归查找左子树。
• 若key大于Tree->data，则递归查找右子树。

【算法代码】

欢迎大家来到IT世界,在知识的湖畔探索吧!BiTree Find(BiTree Tree, ElemType key) { if (nullptr == Tree) { return nullptr; } else if (Tree->data > key) /*查找左子树*/ { return Find(Tree->lchild, key); } else if (Tree->data < key) /*查找右子树*/ { return Find(Tree->rchild, key); } else/*查找的key*/ { return Tree; } }

单个结点的插入和查询复杂度为。

二叉排序树的删除

二叉排序树的结点删除包括两个过程，查找和删除。结点的删除有以下三种情况：

• 待删除结点度为0。
• 待删除结点度为1。
• 待删除结点度为2。

【场景1】

第一种情况如下图4所示，待删除节点值为 “6”，该结点无子树，删除后并不影响二叉排序树的结构特性，可以直接删除。即二叉排序树中待删除结点度为零时，该结点为叶子结点，可以直接删除：

图4 单结点度为0

【场景2】

第二种情况如下图5所示，待删除结点值为“7”，该结点有一个左子树，删除结点后，为了维持二叉排序树结构特性，需要将左子树“上移”到删除的结点位置上，即二叉排序树中待删除的结点度为1时；可以将待删除结点的左子树或右子树“上移”到删除结点位置上，以此来满足二叉排序树的结构特性。

图5 单结点度为1

【场景3】

第三种情况如下图6所示，待删除的结点值为 “9”，该结点既有左子树，也有右子树，删除结点后，为了维持二叉排序树的结构特性，需要从其左子树中选出一个最大值的结点，“上移”到删除的结点位置上。即二叉排序树中待删除结点的度为2时，可以将待删除结点的左子树中的最大值结点“移动”到删除结点位置上，以此来满足二叉排序树的结构特性。操作过程：

• 查找出左子树中的最大值结点。
• 替换待删除结点node的值为的值。
• 删除结点。

因为为左子树的最大值结点，所以结点的度一定是0或1，所以删除结点的情况就转移为场景1和2两种情况。

图6 单结点度为2

单个结点的删除复杂度为。

【算法代码】

BiTree BSTDelete(BiTree& Tree, ElemType key) { if (nullptr == Tree) { return nullptr; } else if (Tree->data > key)/*在该结点左子树查找结点key*/ { Tree->lchild = BSTDelete(Tree->lchild, key); } else if (Tree->data < key)/*在该结点右子树查找结点key*/ { Tree->rchild = BSTDelete(Tree->rchild, key); } else /*找到结点key*/ { if (Tree->lchild && Tree->rchild) /*同时拥有左右子树*/ { /*找到左子树最大值*/ BiTNode* Max = FindMax(Tree->lchild);/*左子树找到最大值结点*/ Tree->data = Max->data;/*用左子树最大值替换当前结点值*/ Tree->lchild = BSTDelete(Tree->lchild, Max->data);/*删除左子树最大值结点*/ } else if (!Tree->lchild && Tree->rchild) /*只有右子树*/ { BiTNode* Node = Tree; Tree = Tree->rchild; free(Node); } else if (Tree->lchild && !Tree->rchild) /*只有左子树*/ { BiTNode* Node = Tree; Tree = Tree->lchild; free(Node); } else /*没有左右子树*/ { free(Tree); Tree = nullptr; } } return Tree; }

二叉排序树查找最小值

二叉排序树的最小值在左子树，最小值结点的度一定是0或1。图1中最小值为0。

【算法代码】

欢迎大家来到IT世界,在知识的湖畔探索吧!BiTree FindMin(BiTree Tree) { if (nullptr == Tree) { return nullptr; } else if (nullptr == Tree->lchild) { return Tree; } else { return FindMin(Tree->lchild); } }

二叉排序树查找最大值

二叉排序树的最大值在右子树，最大值结点的度一定是0或1。图1中最大值为9。

【算法代码】

BiTree FindMax(BiTree Tree) { if (nullptr == Tree) { return nullptr; } else if (nullptr == Tree->rchild) { return Tree; } else { return FindMax(Tree->rchild); } }