目录二叉搜索树二叉搜索树概念​编辑二叉搜索树操作二叉搜索树的查找二叉搜索树的插入二叉搜索树的删除二叉搜索树的实现声明1 构造函数2 析构函数3 查找节点4 插入节点5 删除节点6 中序遍历完整代码二叉搜索树的应用性能分析二叉树进阶面试题二叉搜索树二叉搜索树概念二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:a.若它的左子树不为空则左子树上所有节点的值都小于根节点的值b.若它的右子树不为空则右子树上所有节点的值都大于根节点的值c.它的左右子树也分别为二叉搜索树二叉搜索树操作int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};二叉搜索树的查找a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。b、最多查找高度次走到到空还没找到这个值不存在。二叉搜索树的插入插入的具体过程如下a. 树为空则直接新增节点赋值给root指针b. 树不空按二叉搜索树性质查找插入位置插入新节点二叉搜索树的删除首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况a. 要删除的结点无孩子结点b. 要删除的结点只有左孩子结点c. 要删除的结点只有右孩子结点d. 要删除的结点有左、右孩子结点看似删除节点有4种情况但实际上a和b和c可以合并这样就只有2种情况了a:待删除的结点无孩子/只有一个孩子删除结点并使父亲结点指向被删除结点的孩子结点无孩子视为孩子是空结点任意指向一个即可b:待删除的结点有左右孩子采用替换法寻找删除结点右子树的最小结点右子树最左结点将最小结点的值和删除结点的值替换然后删除最小结点此时最小结点要么没有孩子要么只有一个孩子符合a情况可以直接删除二叉搜索树的实现声明templateclass T struct BSTNode { BSTNode(const T data T()) : _pLeft(nullptr), _pRight(nullptr), _data(data) {} BSTNodeT* _pLeft; BSTNodeT* _pRight; T _data; }; templateclass T class BSTree { typedef BSTNodeT Node; typedef Node* PNode; public: BSTree(); // 构造函数 ~BSTree(); // 析构函数 PNode Find(const T data); // 查找值为data的节点 bool Insert(const T data); // 插入节点 bool Erase(const T data); // 删除节点 void InOrder(); // 中序遍历打印 private: PNode _pRoot; void _Destroy(PNode root); // 递归销毁 void _InOrder(PNode root); // 递归中序遍历 };1 构造函数初始化根节点为空templateclass T BSTreeT::BSTree() : _pRoot(nullptr) {}2 析构函数递归释放所有节点防止内存泄漏templateclass T void BSTreeT::_Destroy(PNode root) { if (root nullptr) return; _Destroy(root-_pLeft); _Destroy(root-_pRight); delete root; root nullptr; } templateclass T BSTreeT::~BSTree() { _Destroy(_pRoot); }3 查找节点根据二叉搜索树性质从根开始比较小于向左大于向右相等则返回节点指针templateclass T typename BSTreeT::PNode BSTreeT::Find(const T data) { PNode cur _pRoot; while (cur) { if (data cur-_data) cur cur-_pLeft; else if (data cur-_data) cur cur-_pRight; else return cur; // 找到 } return nullptr; // 未找到 }4 插入节点空树则直接插入根节点否则找到合适位置叶子节点下方插入新节点templateclass T bool BSTreeT::Insert(const T data) { if (_pRoot nullptr) { _pRoot new Node(data); return true; } PNode cur _pRoot; PNode parent nullptr; // 查找插入位置 while (cur) { parent cur; if (data cur-_data) cur cur-_pLeft; else if (data cur-_data) cur cur-_pRight; else return false; // 已存在插入失败 } // 创建新节点并连接到父节点 PNode newNode new Node(data); if (data parent-_data) parent-_pLeft newNode; else parent-_pRight newNode; return true; }5 删除节点先查找待删除节点若不存在则返回false。删除分三种情况只有左孩子或无孩子让父节点指向左孩子然后删除该节点只有右孩子让父节点指向右孩子然后删除该节点左右孩子都存在找到右子树的最小节点或左子树的最大节点用其值覆盖待删除节点再递归删除该替代节点转变为前两种情况templateclass T bool BSTreeT::Erase(const T data) { if (_pRoot nullptr) return false; // 1. 查找待删除节点及其父节点 PNode cur _pRoot; PNode parent nullptr; while (cur) { if (data cur-_data) break; parent cur; if (data cur-_data) cur cur-_pLeft; else cur cur-_pRight; } if (cur nullptr) // 未找到 return false; // 2. 情况1只有右孩子或为叶子处理叶子时右孩子为空左孩子也为空 if (cur-_pLeft nullptr) { // 若删除的是根节点特殊处理 if (parent nullptr) _pRoot cur-_pRight; else if (cur parent-_pLeft) parent-_pLeft cur-_pRight; else parent-_pRight cur-_pRight; delete cur; } // 情况2只有左孩子 else if (cur-_pRight nullptr) { if (parent nullptr) _pRoot cur-_pLeft; else if (cur parent-_pLeft) parent-_pLeft cur-_pLeft; else parent-_pRight cur-_pLeft; delete cur; } // 情况3左右孩子都存在 else { // 找右子树中最小的节点最左 PNode minParent cur; PNode minNode cur-_pRight; while (minNode-_pLeft) { minParent minNode; minNode minNode-_pLeft; } // 覆盖值 cur-_data minNode-_data; // 删除minNode它一定没有左孩子按情况1处理 if (minParent-_pLeft minNode) minParent-_pLeft minNode-_pRight; else minParent-_pRight minNode-_pRight; delete minNode; } return true; }6 中序遍历递归遍历左-根-右可得到升序序列templateclass T void BSTreeT::_InOrder(PNode root) { if (root nullptr) return; _InOrder(root-_pLeft); std::cout root-_data ; _InOrder(root-_pRight); } templateclass T void BSTreeT::InOrder() { _InOrder(_pRoot); std::cout std::endl; }完整代码#include iostream using namespace std; templateclass T struct BSTNode { BSTNode(const T data T()) : _pLeft(nullptr), _pRight(nullptr), _data(data) {} BSTNodeT* _pLeft; BSTNodeT* _pRight; T _data; }; templateclass T class BSTree { typedef BSTNodeT Node; typedef Node* PNode; public: BSTree(); ~BSTree(); PNode Find(const T data); bool Insert(const T data); bool Erase(const T data); void InOrder(); private: PNode _pRoot; void _Destroy(PNode root); void _InOrder(PNode root); }; // 构造函数 templateclass T BSTreeT::BSTree() : _pRoot(nullptr) {} // 析构辅助函数 templateclass T void BSTreeT::_Destroy(PNode root) { if (root nullptr) return; _Destroy(root-_pLeft); _Destroy(root-_pRight); delete root; root nullptr; } // 析构函数 templateclass T BSTreeT::~BSTree() { _Destroy(_pRoot); } // 查找 templateclass T typename BSTreeT::PNode BSTreeT::Find(const T data) { PNode cur _pRoot; while (cur) { if (data cur-_data) cur cur-_pLeft; else if (data cur-_data) cur cur-_pRight; else return cur; } return nullptr; } // 插入 templateclass T bool BSTreeT::Insert(const T data) { if (_pRoot nullptr) { _pRoot new Node(data); return true; } PNode cur _pRoot; PNode parent nullptr; while (cur) { parent cur; if (data cur-_data) cur cur-_pLeft; else if (data cur-_data) cur cur-_pRight; else return false; } PNode newNode new Node(data); if (data parent-_data) parent-_pLeft newNode; else parent-_pRight newNode; return true; } // 删除 templateclass T bool BSTreeT::Erase(const T data) { if (_pRoot nullptr) return false; PNode cur _pRoot; PNode parent nullptr; while (cur) { if (data cur-_data) break; parent cur; if (data cur-_data) cur cur-_pLeft; else cur cur-_pRight; } if (cur nullptr) return false; // 只有右孩子或叶子 if (cur-_pLeft nullptr) { if (parent nullptr) _pRoot cur-_pRight; else if (cur parent-_pLeft) parent-_pLeft cur-_pRight; else parent-_pRight cur-_pRight; delete cur; } // 只有左孩子 else if (cur-_pRight nullptr) { if (parent nullptr) _pRoot cur-_pLeft; else if (cur parent-_pLeft) parent-_pLeft cur-_pLeft; else parent-_pRight cur-_pLeft; delete cur; } // 左右孩子都有 else { PNode minParent cur; PNode minNode cur-_pRight; while (minNode-_pLeft) { minParent minNode; minNode minNode-_pLeft; } cur-_data minNode-_data; if (minParent-_pLeft minNode) minParent-_pLeft minNode-_pRight; else minParent-_pRight minNode-_pRight; delete minNode; } return true; } // 中序遍历辅助 templateclass T void BSTreeT::_InOrder(PNode root) { if (root nullptr) return; _InOrder(root-_pLeft); cout root-_data ; _InOrder(root-_pRight); } // 中序遍历 templateclass T void BSTreeT::InOrder() { _InOrder(_pRoot); cout endl; } // 测试 int main() { BSTreeint bst; bst.Insert(5); bst.Insert(3); bst.Insert(7); bst.Insert(1); bst.Insert(4); bst.Insert(6); bst.Insert(8); cout 中序遍历: ; bst.InOrder(); // 1 3 4 5 6 7 8 cout 查找4: (bst.Find(4) ? 找到 : 未找到) endl; cout 查找9: (bst.Find(9) ? 找到 : 未找到) endl; bst.Erase(5); cout 删除5后: ; bst.InOrder(); // 1 3 4 6 7 8 bst.Erase(1); cout 删除1后: ; bst.InOrder(); // 3 4 6 7 8 return 0; }二叉搜索树的应用1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。比如给一个单词word判断该单词是否拼写正确具体方式如下a.以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树b.在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。2. KV模型每一个关键码key都有与之对应的值Value即的键值对。该种方 式在现实生活中非常常见a.比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文就构成一种键值对b.再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是就构成一种键值对。性能分析插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树最好情况如果二叉搜索树接近完全二叉树那么树高大约是log₂N平均比较次数也是log₂N。这时 BST 很高效。最坏情况如果插入顺序很差比如有序插入1, 2, 3, 4, 5。那 BST 会退化成一条链因为 BST不自平衡。这时平均比较次数接近N/2。也就是说本来希望像二分查找一样快结果退化后接近顺序查找这就是 BST 最大的问题。能不能不管按什么顺序插入都让性能保持接近最优答案就是AVL 树红黑树它们的作用就是在插入删除后尽量维持树的平衡避免退化。二叉树进阶面试题1. 二叉树创建字符串。606. 根据二叉树创建字符串 - 力扣LeetCode2. 二叉树的分层遍历1。102. 二叉树的层序遍历 - 力扣LeetCode3. 二叉树的分层遍历2。107. 二叉树的层序遍历 II - 力扣LeetCode4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。236. 二叉树的最近公共祖先 - 力扣LeetCode5. 二叉树搜索树转换成排序双向链表。二叉搜索树与双向链表_牛客题霸_牛客网6. 根据一棵树的前序遍历与中序遍历构造二叉树。 105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode7. 根据一棵树的中序遍历与后序遍历构造二叉树。106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode8. 二叉树的前序遍历非递归迭代实现 。144. 二叉树的前序遍历 - 力扣LeetCode9. 二叉树中序遍历 非递归迭代实现。94. 二叉树的中序遍历 - 力扣LeetCode10. 二叉树的后序遍历 非递归迭代实现。145. 二叉树的后序遍历 - 力扣LeetCode