文章目录
一、二叉排序树的概念
1.BST树的定义：二叉排序树，二叉搜索树。
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
- 每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。
- 左子树(如果存在)上所有结点的关键码都小于根结点的关键码。
- 右子树(如果存在)上所有结点的关键码都大于根结点的关键码。
- 左子树和右子树也是二叉搜索树。
2.特性：如果对一个BST树进行中序遍历，得到的结果是各个结点的关键码按照从小到大的顺序排列，所以称为二叉搜索树或二叉排序树。
图示：
二、二叉排序树的结构设计
二叉排序树有四个域：关键码、双亲指针，左子树指针、右子树指针。
typedef int KeyType;
typedef struct BstNode
{
KeyType val;
BstNode* leftchild;
BstNode* parent;
BstNode* rightchild;
}BstNode, *BSTree;
三、构造二叉排序树
1.Insert()函数
给定根节点和一个值，插入到该树中。
该函数的编写需要考虑这些方面：
- 如果根节点为NULL，那么需要构造根节点，我们就提供一个MakeRoot()函数，再提供一个创建节点函数BuyNode()。
- 定义两个跟踪指针，一个表示双亲结点pa，一个表示当前结点p。
- 使用while循环，如果p为NULL就退出，否则让pa指向当前结点p，然后p向下走，根据二叉排序树的特性，p指向合适的左右子树。
- 如果循环退出，那么有两种情况，要么p为NULL，要么当前合适的位置的关键码key和待插入数据相等，这时候直接返回假。
- 经过3、4步骤还没返回，说明要到了该插入的位置，这时候让p构造新节点，让待插入元素为它的关键码域，双亲为pa指针；
- 再根据关键码的大小，将p挂到合适的左右子树；
- 插入成功返回true。
注意点：
为什么参数是 *&？
因为传入的是指针root，如果只是对参数的指针ptr改变了指向，那么原始指针root的指向并没有改变，所以需要传指针的引用。
BstNode* BuyNode()
{
BstNode* s = (BstNode*)malloc(sizeof(BstNode));
if (s == nullptr) exit(1);
memset(s, 0, sizeof(BstNode));
return s;
}
BstNode* MakeRoot(KeyType kx)
{
BstNode* root = BuyNode();
root->key = kx;
return root;
}
bool Insert(BstNode*& ptr, KeyType kx)
{
if (ptr == nullptr) // 1
{
ptr = MakeRoot(kx);
return true;
}
// 两个跟踪指针 2
BstNode* pa = nullptr;
BstNode* p = ptr;
while (p != nullptr && p->key != kx) // 3
{
pa = p;
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p != nullptr && p->key == kx) return false; // 4
p = BuyNode(); // 5
p->key = kx;
p->parent = pa;
if (p->key < pa->key) // 6
pa->leftchild = p;
else
pa->rightchild = p;
return true; // 7
}
示例：
void InOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
InOrder(ptr->leftchild);
cout << ptr->key << " ";
InOrder(ptr->rightchild);
}
}
int main(void)
{
BSTree root = nullptr;
int nums[] = { 53, 17, 78, 9, 45, 65, 87, 23, 81, 94, 88 };
int n = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < n; ++i)
{
cout << Insert(root, nums[i]) << " ";
}
cout << endl;
InOrder(root);
cout << endl;
return 0;
}
使用中序遍历，得到的结果是从小到大的顺序输出，说明构造二叉排序树成功了。
2.insert改进
在运行过程中，
- 发现如果传进来的根节点为NULL，那么可以直接不写第一步，让p指向ptr后，while循环直接不执行，会跳过while和第一个if语句，直接让p去申请新节点。
- 如果pa为NULL，表明当前的树还没有根节点，就让ptr指向p刚申请的结点，表示ptr插入了根节点，就返回true。
- 等待下一次的insert()。
bool Insert(BstNode*& ptr, KeyType kx)
{
// 两个跟踪指针
BstNode* pa = nullptr;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
pa = p;
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p != nullptr && p->key == kx) return false;
p = BuyNode();
p->key = kx;
p->parent = pa;
if (pa == nullptr)
{
ptr = p;
}
else
{
if (p->key < pa->key)
pa->leftchild = p;
else
pa->rightchild = p;
}
return true;
}
运行示例：还是会输出正确的内容
四、非递归中序遍历的准备
1. 找到最小关键码的结点 First()
二叉排序树的最小值，即就是树的最左端结点的关键码，那么可以一直访问左子树来达到目的。
BstNode* First(BstNode* ptr) // min
{
while (ptr != nullptr && ptr->leftchild != nullptr)
{
ptr = ptr->leftchild;
}
return ptr;
}
运行示例：对于上述例子构造的二叉树来说，最小结点是关键码为9这个结点
2. 找到当前结点的后继结点 Next()
这个函数的实现比上面的要难一点，不过根据图示的话会好想到。
需要考虑到的方面：
- 如果当前结点为NULL，则返回。
- 如果当前结点的右子树不为NULL，那么它的后继肯定在右子树，那么可以利用First()来找到右子树的最小值，这个最小值就是它的后继结点。 例如上图中的 17，它的右子树不为NULL，那么右子树的最小关键码 23就是它的后继结点，利用First()函数得到。
- 如果右子树为NULL，则利用一个指针pa当作双亲指针，利用while循环，如果pa不为NULL且pa的左子树不等于ptr，就让pa和ptr往上走。
- 如果循环退出了，说明有两个原因，第一要么pa为NULL，说明该结点是最大结点，没有next域了；例如上图中的94。第二是当前节点ptr正好在双亲结点的左子树，那么直接返回双亲结点即可。例如上图中的9、81等。
BstNode* Next(BstNode* ptr)
{
if (ptr == nullptr) return ptr; // 1
if (ptr->rightchild != nullptr) // 2
{
return First(ptr->rightchild);
}
else
{
BstNode* pa = ptr->parent;
while (pa != nullptr && pa->leftchild != ptr) // 3
{
ptr = pa;
pa = ptr->parent;
}
return pa; // 4
}
}
3. 找到最大关键码结点 Last()
最大关键码结点正好和First()相反，根据图示也可以看出，找到最右边结点即可。
BstNode* Last(BstNode* ptr) // max
{
while (ptr != nullptr && ptr->rightchild != nullptr)
{
ptr = ptr->rightchild;
}
return ptr;
}
4. 找到当前节点的前驱 Prev()
和上面的Next()函数刚好相反，此函数的步骤可以参考Next()
需要考虑到的方面：
- 如果当前结点为NULL，则返回。
- 如果当前结点的左子树不为NULL，那么它的前驱肯定在左子树，那么可以利用Last()来找到左子树的最大值，这个最大值就是它的前驱结点。 例如上图中的 17，它的左子树不为NULL，那么左子树的最大关键码 9就是它的前驱结点，利用Last()函数得到。
- 如果左子树为NULL，则利用一个指针pa当作双亲指针，利用while循环，如果pa不为NULL且pa的右子树不等于ptr，就让pa和ptr往上走。
- 如果循环退出了，说明有两个原因，第一要么pa为NULL，说明该结点是最小结点，没有prev域了；例如上图中的 9 。第二是当前节点ptr正好在双亲结点的右子树，那么直接返回双亲结点即可。例如上图中的94、78等。
BstNode* Prev(BstNode* ptr)
{
if (ptr == nullptr) return ptr; // 1
if (ptr->leftchild != nullptr) // 2
{
return Last(ptr->leftchild);
}
else
{
BstNode* pa = ptr->parent; // 3
while (pa != nullptr && pa->rightchild != ptr)
{
ptr = pa;
pa = ptr->parent;
}
return pa; // 4
}
}
五、非递归中序遍历
利用上述实现的函数，掌握了最小值和最大值，前驱和后继，那么遍历函数会很好写。
1. 顺序遍历
void NiceInOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
for (BstNode* p = First(ptr); p != nullptr; p = Next(p))
{
cout << p->key << " ";
}
cout << endl;
}
}
2. 逆序遍历
void ReNiceInOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
for (BstNode* p = Last(ptr); p != nullptr; p = Prev(p))
{
cout << p->key << " ";
}
cout << endl;
}
}
运行示例：
六、移除函数 Remove()
给定待删除的关键码值和根节点，删除与之对应的结点。
经过分析，可能会出现六种情况：
伪代码：
1. root == nullptr
2. Findval is not exist
has found
3. leaf
4. brch
5. two brch -> brch left
6. root -> new root
1.根节点为NULL
- 如果根节点为NULL，则直接返回。
bool Remove(BstNode* ptr, KeyType kx)
{
if (ptr == nullptr) return false;
}
2. 没找到对应的关键码
- 如果没找到对应的关键码，直接返回。
利用while循环，如果p为NULL，说明没找到，返回假。
bool Remove(BstNode* ptr, KeyType kx)
{
if (ptr == nullptr) return false;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p == nullptr) return false; // 没找到
}
3.删除叶子结点
- 找到要删除的结点了，而且是叶子结点
让指针pa为当前带删除结点的双亲结点，判断p是左子树还是右子树，将其置为NULL，并free()掉。返回真。
// p is leaf
BstNode* pa = p->parent;
if (pa->leftchild == p)
{
pa->leftchild = nullptr;
}
else
{
pa->rightchild = nullptr;
}
free(p);
return true;
4.删除具有单分支的结点
- 找到待删除的结点，是具有单分支的结点。
图示：
45为待删除的结点p，那么除了它的双亲结点，还要找到左右子树child，由于是单分支，所以不是左边就是右边；如果子树child不为NULL，先将其的双亲指向p的双亲；再判断p结点是pa的左子树还是右子树，将child结点挂在上面；free()掉 p结点，返回真。
// p is leaf || p is brch
BstNode* pa = p->parent;
BstNode* child = p->leftchild != nullptr ? p->leftchild : p->rightchild;
if (child != nullptr) child->parent = pa;
if (pa->leftchild == p)
{
pa->leftchild = child;
}
else
{
pa->rightchild = child;
}
free(p);
return true;
5.删除具有双分支的结点
- 如果要删除具有双分支的结点，这里直接拿根节点示例
删除方法是“狸猫换太子”，找到根节点右子树的最小值（利用First()），将根节点的值和该结点的值交换，然后删除该结点。
if (ptr == nullptr) return false;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p == nullptr) return false; // 没找到
if (p->leftchild != nullptr && p->rightchild != nullptr)
{
BstNode* nextNode = First(p->rightchild);
p->key = nextNode->key;
p = nextNode;
}
6.删除的是根节点，且只有单分支
- 如果删除的是根节点，且只有单分支，示例：
那么判断出根节点双亲为NULL后，就需要将右子树的最小值设置为新根结点。需要加一步判断。
BstNode* pa = p->parent;
BstNode* child = p->leftchild != nullptr ? p->leftchild : p->rightchild;
if (child != nullptr) child->parent = pa;
if (pa == nullptr) // 加入这一步
{
ptr = child;
}
else
{
if (pa->leftchild == p)
{
pa->leftchild = child;
}
else
{
pa->rightchild = child;
}
}
free(p);
return true;
Remove()最终代码
bool Remove(BstNode*& ptr, KeyType kx)
{
// 1.如果根为NULL
if (ptr == nullptr) return false;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p == nullptr) return false; // 2.没找到
// 删除根节点且双分支
if (p->leftchild != nullptr && p->rightchild != nullptr)
{
BstNode* nextNode = First(p->rightchild);
p->key = nextNode->key;
p = nextNode;
}
// 删除但分支
BstNode* pa = p->parent;
BstNode* child = p->leftchild != nullptr ? p->leftchild : p->rightchild;
if (child != nullptr) child->parent = pa;
if (pa == nullptr) // 单分支且是根节点
{
ptr = child;
}
else
{
if (pa->leftchild == p)
{
pa->leftchild = child;
}
else
{
pa->rightchild = child;
}
}
free(p);
return true;
}
运行示例：这里删除的是根节点
int main(void)
{
BSTree root = nullptr;
int nums[] = { 53, 17, 78, 9, 45, 65, 87, 23, 81, 94, 88 };
int n = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < n; ++i)
{
cout << Insert(root, nums[i]) << " ";
}
cout << endl;
NiceInOrder(root);
cout << endl;
ReNiceInOrder(root);
cout << endl;
cout << Remove(root, 53) << endl;;
NiceInOrder(root);
return 0;
}
END所用代码
// BST树
typedef int KeyType;
typedef struct BstNode
{
KeyType key;
BstNode* leftchild;
BstNode* parent;
BstNode* rightchild;
}BstNode, *BSTree;
BstNode* BuyNode()
{
BstNode* s = (BstNode*)malloc(sizeof(BstNode));
if (s == nullptr) exit(1);
memset(s, 0, sizeof(BstNode));
return s;
}
BstNode* MakeRoot(KeyType kx)
{
BstNode* root = BuyNode();
root->key = kx;
return root;
}
bool Insert(BstNode*& ptr, KeyType kx)
{
// 两个跟踪指针
BstNode* pa = nullptr;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
pa = p;
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p != nullptr && p->key == kx) return false;
p = BuyNode();
p->key = kx;
p->parent = pa;
if (pa == nullptr)
{
ptr = p;
}
else
{
if (p->key < pa->key)
pa->leftchild = p;
else
pa->rightchild = p;
}
return true;
}
void InOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
InOrder(ptr->leftchild);
cout << ptr->key << " ";
InOrder(ptr->rightchild);
}
}
BstNode* First(BstNode* ptr) // min
{
while (ptr != nullptr && ptr->leftchild != nullptr)
{
ptr = ptr->leftchild;
}
return ptr;
}
BstNode* Next(BstNode* ptr)
{
if (ptr == nullptr) return ptr;
if (ptr->rightchild != nullptr)
{
return First(ptr->rightchild);
}
else
{
BstNode* pa = ptr->parent;
while (pa != nullptr && pa->leftchild != ptr)
{
ptr = pa;
pa = ptr->parent;
}
return pa;
}
}
BstNode* Last(BstNode* ptr) // max
{
while (ptr != nullptr && ptr->rightchild != nullptr)
{
ptr = ptr->rightchild;
}
return ptr;
}
BstNode* Prev(BstNode* ptr)
{
if (ptr == nullptr) return ptr;
if (ptr->leftchild != nullptr)
{
return Last(ptr->leftchild);
}
else
{
BstNode* pa = ptr->parent;
while (pa != nullptr && pa->rightchild != ptr)
{
ptr = pa;
pa = ptr->parent;
}
return pa;
}
}
void NiceInOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
for (BstNode* p = First(ptr); p != nullptr; p = Next(p))
{
cout << p->key << " ";
}
cout << endl;
}
}
void ReNiceInOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
for (BstNode* p = Last(ptr); p != nullptr; p = Prev(p))
{
cout << p->key << " ";
}
cout << endl;
}
}
/*
root == nullptr;
FindValue not val
Find
1. leaf
2. brch
3. two brch -> brch || leaf
4. root -> new root
*/
bool Remove(BstNode*& ptr, KeyType kx)
{
if (ptr == nullptr) return false;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p == nullptr) return false; // 没找到
if (p->leftchild != nullptr && p->rightchild != nullptr)
{
BstNode* nextNode = First(p->rightchild);
p->key = nextNode->key;
p = nextNode;
}
BstNode* pa = p->parent;
BstNode* child = p->leftchild != nullptr ? p->leftchild : p->rightchild;
if (child != nullptr) child->parent = pa;
if (pa == nullptr)
{
ptr = child;
}
else
{
if (pa->leftchild == p)
{
pa->leftchild = child;
}
else
{
pa->rightchild = child;
}
}
free(p);
return true;
}
int main(void)
{
BSTree root = nullptr;
int nums[] = { 53, 17, 78, 9, 45, 65, 87, 23, 81, 94, 88 };
int n = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < n; ++i)
{
cout << Insert(root, nums[i]) << " ";
}
cout << endl;
NiceInOrder(root);
cout << endl;
ReNiceInOrder(root);
cout << endl;
cout << Remove(root, 53) << endl;
NiceInOrder(root);
return 0;
}
