数据结构 - 二叉查找树 Binary Search Tree 数据结构

目录：

一、性质
二、结点定义
三、部分操作
- 插入:唯一键值和重复键值
- 删除：普通删除和懒惰删除
- 四种遍历：先、中、后序、层级
四、进一步思考

一、二叉查找树性质

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
树中没有键值相等的节点。

二、结点定义

struct TreeNode{ int value; TreeNode *left, *right; TreeNode(int val): value(val), left(NULL), right(NULL){} };

三、部分操作 3.1插入
3.1.1 唯一键值结点的插入递归插入即可。

void SearchTree::Insert(int val){ root = RecursiveInsert(val, root); }TreeNode* SearchTree::RecursiveInsert(int val, TreeNode* head){ if(!head){return new TreeNode(val); } if(val > head->value){ head->right = RecursiveInsert(val, head->right); } else if(val < head->value){ head->left = RecursiveInsert(val, head->left); } return head; }

3.1.2 支持重复键值结点的插入如果键值是包含在简单的数据结构中，只需要额外一个记录频次的变量。
如果键值时包含在庞大的数据结构中，可以将相同键值存储到辅助数据结构中，比如链表、另一个查找树。
3.2 删除
3.2.1 唯一键值结点删除

递归找到删除结点
将它的值由其右子树最小值或者左子树最大值替换
然后递归删除右子树最小值结点/左子树最大值结点

void SearchTree::Delete(int val){ RecursiveDelete(val, root); }TreeNode* SearchTree::RecursiveDelete(int val, TreeNode* head){ if(!head) return NULL; if(head->value < val){ head->right = RecursiveDelete(val, head->right); } else if(head->value > val){ head->left = RecursiveDelete(val, head->left); } else{ if(head->left && head->right){ head->value = https://www.it610.com/article/RecursiveMin(head->right)->value; head->right = RecursiveDelete(head->value, head->right); } else{ TreeNode* tmp = head; if(!head->left) head = head->right; else if(!head->right) head = head->left; delete tmp; tmp = NULL; } } return head; }

3.2.2 懒惰删除->重复键值结点删除如果删除的结点比较少，可以用懒惰删除法。当一个结点要被删除，它仍可以被保留在tree中，只是被标记成删除的状态。而且，即便树有一半的结点被标记为删除状态，时间上的浪费也只是常数。
这个方法很适用于当树允许重复的结点出现时的情况。允许重复结点的树有记录频次的变量，删除一个结点，相当把这个变量减一，也就相当于mark了。
3.3 四种遍历
3.3.1 先序遍历 Preorder 顺序：父结点->左子树->右子树。

void SearchTree::PrintPreorder(){ Preorder(root); }void SearchTree::Preorder(TreeNode* head){ if(!head) return; cout << head->value << " "; Preorder(head->left); Preorder(head->right); }

3.3.2 中序遍历 Inorder 顺序：左子树->父结点->右子树。

void SearchTree::PrintInorder(){ Inorder(root); }void SearchTree::Inorder(TreeNode* head){ if(!head) return; Inorder(head->left); cout << head->value << " "; Inorder(head->right); }

3.3.3 后序遍历 Postorder 顺序：左子树->右子树->父结点。

void SearchTree::PrintPostorder(){ Postorder(root); }void SearchTree::Postorder(TreeNode* head){ if(!head) return; Postorder(head->left); Postorder(head->right); cout << head->value << " "; }

3.3.4 层级遍历 Level Order 按照结点深度遍历，即先打印深度为0也就是结点，然后打印深度为1的结点，依次递推。
不同于前面三个遍历每次打印单个结点，层级遍历每一次需要打印一层结点，而结点之间从结构上，没有连接，主要通过父结点的左右指针访问。
因此，我们需要用到一个容器类变量，保存上一层的父结点。这里我选择用queue<>，遍历操作从队列前端执行，更新push操作从队列后端执行，如下所示。

void SearchTree::PrintLevelorder(){ if(!root) return; queue nodeQueue; nodeQueue.push(root); Levelorder(nodeQueue); }void SearchTree::Levelorder(queue &nodeQueue){ if(nodeQueue.empty()) return; int size = nodeQueue.size(); TreeNode* cur = NULL; while(size--){ cur = nodeQueue.front(); cout << cur->value << " "; nodeQueue.pop(); if(cur->left) nodeQueue.push(cur->left); if(cur->right) nodeQueue.push(cur->right); } return Levelorder(nodeQueue); }

3.4 完整C++实现

#include #include #include using namespace std; struct TreeNode{ int value; TreeNode *left, *right; TreeNode(int val): value(val), left(NULL), right(NULL){} }; class SearchTree { public: SearchTree():root(NULL){} SearchTree(vector &arr); void PrintPreorder(); void PrintInorder(); void PrintPostorder(); void PrintLevelorder(); void Insert(int val); void Delete(int val); TreeNode* Find(int val); TreeNode* Min(); void Clear(); private: void Preorder(TreeNode* head); void Inorder(TreeNode* head); void Postorder(TreeNode* head); void Levelorder(queue &nodeQueue); TreeNode* RecursiveInsert(int val, TreeNode* head); TreeNode* RecursiveDelete(int val, TreeNode* head); TreeNode* RecursiveFind(int val, TreeNode* head); TreeNode* RecursiveMin(TreeNode* head); TreeNode* RecursiveClear(TreeNode* &head); TreeNode* root; }; SearchTree::SearchTree(vector &arr){ for(auto i: arr) Insert(i); }void SearchTree::Insert(int val){ root = RecursiveInsert(val, root); }TreeNode* SearchTree::RecursiveInsert(int val, TreeNode* head){ if(!head){return new TreeNode(val); } if(val > head->value){ head->right = RecursiveInsert(val, head->right); } else if(val < head->value){ head->left = RecursiveInsert(val, head->left); } return head; }void SearchTree::Delete(int val){ RecursiveDelete(val, root); }TreeNode* SearchTree::RecursiveDelete(int val, TreeNode* head){ if(!head) return NULL; if(head->value < val){ head->right = RecursiveDelete(val, head->right); } else if(head->value > val){ head->left = RecursiveDelete(val, head->left); } else{ if(head->left && head->right){ head->value = https://www.it610.com/article/RecursiveMin(head->right)->value; head->right = RecursiveDelete(head->value, head->right); } else{ TreeNode* tmp = head; if(!head->left) head = head->right; else if(!head->right) head = head->left; delete tmp; tmp = NULL; } } return head; }TreeNode* SearchTree::Find(int val){ return RecursiveFind(val, root); }TreeNode* SearchTree::RecursiveFind(int val, TreeNode* head){ if(!head) return NULL; if(head->value > val) return RecursiveFind(val, head->left); else if(head->value < val) return RecursiveFind(val, head->right); else return head; }TreeNode* SearchTree::Min(){ return RecursiveMin(root); }TreeNode* SearchTree::RecursiveMin(TreeNode* head){ if(!head) return NULL; if(!head->left) return head; return RecursiveMin(head->left); }void SearchTree::Clear(){ RecursiveClear(root); }TreeNode* SearchTree::RecursiveClear(TreeNode* &head){ if(head){ head->left = RecursiveClear(head->left); head->right = RecursiveClear(head->right); delete head; head = NULL; } return NULL; }void SearchTree::PrintPreorder(){ Preorder(root); }void SearchTree::Preorder(TreeNode* head){ if(!head) return; cout << head->value << " "; Preorder(head->left); Preorder(head->right); }void SearchTree::PrintInorder(){ Inorder(root); }void SearchTree::Inorder(TreeNode* head){ if(!head) return; Inorder(head->left); cout << head->value << " "; Inorder(head->right); }void SearchTree::PrintPostorder(){ Postorder(root); }void SearchTree::Postorder(TreeNode* head){ if(!head) return; Postorder(head->left); Postorder(head->right); cout << head->value << " "; }void SearchTree::PrintLevelorder(){ if(!root) return; queue nodeQueue; nodeQueue.push(root); Levelorder(nodeQueue); }void SearchTree::Levelorder(queue &nodeQueue){ if(nodeQueue.empty()) return; int size = nodeQueue.size(); TreeNode* cur = NULL; while(size--){ cur = nodeQueue.front(); cout << cur->value << " "; nodeQueue.pop(); if(cur->left) nodeQueue.push(cur->left); if(cur->right) nodeQueue.push(cur->right); } return Levelorder(nodeQueue); }int main(){ vector arr = {8, 4, 15, 2, 6, 9, 17}; SearchTree test(arr); //Insertion Test cout << "Before deletion: " << endl; cout << "Preorder: "; test.PrintPreorder(); cout << endl; cout << "Inorder: "; test.PrintInorder(); cout << endl; cout << "Postorder: "; test.PrintPostorder(); cout << endl; cout << "Levelorder: "; test.PrintLevelorder(); cout << endl; test.Delete(8); //Deletion Test cout << "After deletion: "; test.PrintPreorder(); cout << endl; TreeNode* fRet = test.Find(8); //Find Test if(fRet) cout << "Find: " << fRet->value << endl; else cout << "Can't find."<< endl; test.Clear(); //Clear Test test.PrintPreorder(); cout << endl;

四、进一步思考按照以上insert和delete方法，我们发现一定次数后，树容易一个方向倾斜。