二叉排序树(BST)的创建，查找，插入，删除及最大最小结点

本文主要是介绍二叉排序树(BST)的创建，查找，插入，删除及最大最小结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考：https://blog.csdn.net/happyjacob/article/details/82795560

1、什么是二叉排序树

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

1. 非空左子树的所有键值小于其根结点的键值。
2. 非空右子树的所有键值大于其根结点的键值。
3. 左、右子树都是二叉搜索树。

2、二叉搜索树的查找操作

• 查找从根结点开始，如果树为空，返回NULL

• 若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：

  1. 若X小于根结点键值，只需在左子树中继续搜索；
  2. 如果X大于根结点的键值，在右子树中进行继续搜索；
  3. 若两者比较结果是相等，搜索完成，返回指向此结点的指针。

递归实现

//查找，递归实现
BTNode * SearchBST(BTree pT, ElemType key) {if (pT == nullptr)return nullptr;if (key > pT->val) {SearchBST(pT->right, key);}else if(key < pT->val){SearchBST(pT->left, key);}else {return pT;}
}

由于非递归函数的执行效率高，可将“尾递归”函数改为迭代函数

非递归实现

//查找，非递归实现
BTNode * SearchBST(BTree pT, ElemType key) {while (pT != nullptr) {if (key < pT->val) {pT = pT->left;}else if (key > pT->val) {pT = pT->right;}else {return pT;}}return nullptr;
}

3、查找最大和最小元素

最大元素一定是在树的最右分枝的端结点上
最小元素一定是在树的最左分枝的端结点上

//递归寻找最大值
BTNode * findMax(BTree pT) {if (pT == nullptr)return nullptr;else {if (pT->right != nullptr) {findMax(pT->right);}else {return pT;}}
}//非递归寻找最小值
BTNode * findMin(BTree pT) {if (pT == nullptr)return nullptr;while (pT->left != nullptr) {pT = pT->left;}return pT;
}

4、二叉搜索树的插入

关键是要找到元素应该插入的位置，可以采用与Find类似的方法

可以用二叉搜索树的插入来创建二叉搜索树

//二叉搜索树的插入
BTree Insert(BTree pT, ElemType key) {if (pT == nullptr) {BTNode *node = new BTNode(key);}else if (key < pT->val) {pT->left = Insert(pT->left, key);}else if (key > pT->val) {pT->right = Insert(pT->right, key);}else {//节点存在，什么都不做，或者打印信息cout << "节点已经存在" << endl;}return pT;
}

5、二叉搜索树的删除

考虑三种情况：

1. 要删除的结点的左孩子为空：右孩子代替当前结点

     2.要删除的结点的右孩子为空：左孩子代替当前结点

    3.要删除的结点有左、右两棵子树： 用另一结点替代被删除结点：右子树的最小元素 或者 左子树的最大元素

//二叉搜索树的删除
BTree Delete(ElemType x, BTree pT) {if (pT == nullptr) {return nullptr;}if (x > pT->val) {pT->right = Delete(x, pT->right);}else if (x < pT->val) {pT->left = Delete(x, pT->left);}else {if (pT->left && pT->right) {BTNode *tp = findMin(pT->right);pT->val = tp->val;pT->right = Delete(tp->val, pT->right);}else {if (pT->left == nullptr) {pT = pT->right;}else if (pT->right == nullptr) {pT = pT->left;}}	}return pT;
}

完整代码：

#include <iostream>
#include <vector>
#include <deque>using ElemType = int;using namespace std;typedef struct BTNode {ElemType val;struct BTNode *left, *right;BTNode(ElemType x) :val(x), left(nullptr), right(nullptr) {}
}BTNode, *BTree;//查找，递归实现
BTNode * SearchBST(BTree pT, ElemType key) {if (pT == nullptr)return nullptr;if (key > pT->val) {SearchBST(pT->right, key);}else if(key < pT->val){SearchBST(pT->left, key);}else {return pT;}
}//查找，非递归实现
BTNode * SearchBSTNonrecursion(BTree pT, ElemType key) {while (pT != nullptr) {if (key < pT->val) {pT = pT->left;}else if (key > pT->val) {pT = pT->right;}else {return pT;}}return nullptr;
}//查找最大和最小元素
//最大元素一定在树的最右分支的端节点上
//最小元素一定在树的最左分支的端节点上//递归寻找最大值
BTNode * findMax(BTree pT) {if (pT == nullptr)return nullptr;else {if (pT->right != nullptr) {findMax(pT->right);}else {return pT;}}
}//非递归寻找最小值
BTNode * findMin(BTree pT) {if (pT == nullptr)return nullptr;while (pT->left != nullptr) {pT = pT->left;}return pT;
}//二叉搜索树的插入
BTree Insert(BTree pT, ElemType key) {if (pT == nullptr) {pT = new BTNode(key);}else if (key < pT->val) {pT->left = Insert(pT->left, key);}else if (key > pT->val) {pT->right = Insert(pT->right, key);}else {//节点存在，什么都不做，或者打印信息cout << "节点已经存在" << endl;}return pT;
}//二叉搜索树的删除
BTree Delete(ElemType x, BTree pT) {if (pT == nullptr) {return nullptr;}if (x > pT->val) {pT->right = Delete(x, pT->right);}else if (x < pT->val) {pT->left = Delete(x, pT->left);}else {if (pT->left && pT->right) {BTNode *tp = findMin(pT->right);pT->val = tp->val;pT->right = Delete(tp->val, pT->right);}else {if (pT->left == nullptr) {pT = pT->right;}else if (pT->right == nullptr) {pT = pT->left;}}	}return pT;
}void preOrder(BTree pT) {//如果pT == nullptr，则什么也不做if (pT != nullptr) {//此处打印其值，也可以执行其他操作cout << pT->val;preOrder(pT->left);preOrder(pT->right);}
}int main() {//创建一棵平衡二叉树,将以下节点依次插入平衡二叉树vector<int> ivec = { 6, 2, 8, 1, 5, 3, 4 };BTree ptree = nullptr;for (auto i : ivec) {ptree = Insert(ptree, i);}//前序遍历遍历二叉树cout << "前序遍历二叉树：";preOrder(ptree);cout << endl;//删除一个节点，前序遍历ptree = Delete(2, ptree);cout << "删除节点2，再前序遍历：";preOrder(ptree);cout << endl;}

output：

前序遍历二叉树：6215348
删除节点2，再前序遍历：631548
请按任意键继续. . .

 

 

 

 

 

 

 

 

这篇关于二叉排序树(BST)的创建，查找，插入，删除及最大最小结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---