CD66.【C++ Dev】模拟实现二叉搜索树的非递归版本

目录 1.知识回顾 2.练习:在二叉搜索树中查找指定值 3.模拟实现二叉搜索树 框架 初始化 二叉搜索树的构造函数 节点的构造函数 插入节点,不能插入相同的key 中序遍历 查找节点 ★删除节点 画图解释删除的if判断 一般情况 特殊情况 4.练习1: [LintCode]删除二叉查找树的节点 代码 提交结果 6.练习2: [LintCode]在二叉查找树中插入节点 代码 提交结果 5.练习3: 使用二叉搜索树排序 代码 提交结果 6.对比二叉搜索树和有序数组 1.知识回顾 参见 CC40.【C++ Cont】二叉搜索树和平衡二叉树 文章复习基础知识 2.练习:在二叉搜索树中查找指定值 https://www.lintcode.com/problem/1524/?_from=problem_tag&fromId=358 给定一颗二叉搜索树和

. 返回这棵树中值等于

的节点. 如果不存在这样的节点, 返回

. 样例 1:

4 / \ 2 7 / \ 1 3 输出: 节点 2 样例 2:

4 / \ 2 7 / \ 1 3 输出: null 分析: 比较要找的值和根节点的大小关系,沿着二叉搜索树的边遍历就行 代码:

class Solution { public: /** * @param root: the tree * @param val: the val which should be find * @return: the node */ TreeNode* searchBST(TreeNode *root, int val) { while(root) { int root_val=root->val; if (root_val==val) return root; if (root_valright; else root=root->left; } return nullptr; } }; 提交结果:

3.模拟实现二叉搜索树 框架 构建二叉搜索树类和节点类

class Node { public: Node* left; Node* right; K key; }; template class Binary_Search_Tree { typedef Binary_Search_Tree Node; public: //...... private: Node* root; }; 初始化 二叉搜索树的构造函数

:root(nullptr) { } 节点的构造函数

:left(nullptr) ,right(nullptr) ,key(val) { } 插入节点,不能插入相同的key 首先要讨论是否为空树,如果为空是无法遍历树的

{ //分根节点是否为空讨论 if (root) { //...... } else { root = new Node(val); return true; } } 当树不为空时,寻找合适的位置,让cur指针遍历

while (cur) { if (cur->key > val) { cur = cur->left; } else if (cur->key < val) { cur = cur->right; } else//cur->key == val,不能插入相同数字 { return false; } } 当cur为nullptr时,退出循环,但找不到cur对应的根节点,因此还需要一个指针来指向cur的根节点,即 双指针 :

//一开始cur指向树的根节点时,cur是没有父节点的,可以理解为nullptr,当然值也可以不设置 Node* parent = nullptr; while (cur) { if (cur->key > val) { parent = cur; cur = cur->left; } else if (cur->key < val) { parent = cur; cur = cur->right; } else//cur->key == val,不能插入相同数字 { return false; } } return true; 退出循环后,还需要确定parent的左节点还是右节点能插入val

//此时不可能有parent->val == val,前面排除过了 if (parent->key < val) parent->right = cur; else parent->left = cur; 完整代码:

{ //分根节点是否为空讨论 if (root) { Node* cur = root; Node* parent = nullptr;//一开始cur指向树的根节点时,cur是没有父节点的 while (cur) { if (cur->key > val) { parent = cur; cur = cur->left; } else if (cur->key < val) { parent = cur; cur = cur->right; } else//cur->key == val,不能插入相同数字 { return false; } } cur = new Node(val); //此时不可能有parent->val == val,前面排除过了 if (parent->key < val) parent->right = cur; else parent->left = cur; } else { root = new Node(val); } return true; } 中序遍历 中序遍历的复习参见 106.【C语言】数据结构之二叉树的三种递归遍历方式 文章,该文章提供的代码段为:

//按左子树-->根-->右子树的顺序遍历 InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } 但不能直接当做成员函数print_inoder,因为root是私有变量,调用print_inoder函数是不能传参的,因此需要将InOrder写成子函数,然后print_inoder调用InOrder 完整代码:

//按左子树-->根-->右子树的顺序遍历 InOrder(root->left); cout<< root->key<<" "; InOrder(root->right); } Node* root; 测试代码:

int main() { Binary_Search_Tree bst; bst.insert(1); bst.insert(9); bst.insert(10); bst.insert(5); bst.insert(0); bst.insert(7); bst.insert(8); bst.insert(2); bst.insert(5); bst.insert(6); bst.insert(3); bst.insert(4); bst.print_inoder(); return 0; } 运行结果:中序遍历是有序的

查找节点 借鉴插入节点的部分代码:

{ Node* cur = root; while (cur)//cur!=nullptr { if (cur->key > val) cur = cur->left; else if (cur->key < val) cur = cur->right; else //cur->key == val) return true; } return false; } 测试代码:

int main() { Binary_Search_Tree bst; for (int i=0;i<=10;i++) bst.insert(i); if (bst.find(2)) cout << "已找到2" << endl; else cout << "未找到2" << endl; if (bst.find(11)) cout << "已找到11" << endl; else cout << "未找到11" << endl; return 0; } 运行结果:

★删除节点 提醒:删除的节点的key可能不存在 首先要找到节点,借鉴find成员函数的代码

Node* cur = root; //一开始cur指向树的根节点时,cur是没有父节点的,可以理解为nullptr,当然值也可以不设置 Node* parent = nullptr; while (cur) { if (cur == nullptr)//节点不存在 return false; if (cur->key > val) { parent = cur; cur = cur->left; } else if (cur->key < val) { parent = cur; cur = cur->right; } else if (cur->key == val) { //删除节点...... return true; } } //cur为nullptr,没找到 return false; } 再删除节点, 分类讨论: 没有子树、有一个子树、有两个子树 没有子树: 直接delete该节点,然后修改parent->left或parent->right

//...... delete cur; 有一个子树: 要分类讨论是左子树还是右子树 例如要删除3:

循环结束后parent和cur的指向为:

直接将parent->right设置为cur->right

if (cur->left == nullptr) { if (parent->right == cur) parent->right = cur->right; else parent->left = cur->right; } 这样做的前提是parent不为空,如果cur==root是需要单独操作的!

{ //让删除的节点的左子树或右子树直接替代其位置,需要parent if (cur->left == nullptr) { if (cur == root) { root = cur->right; } if (parent->right == cur) parent->right = cur->right; else parent->left = cur->right; } if (cur->right == nullptr) { if (cur == root) { root = cur->left; } if (parent->right == cur) parent->right = cur->left; else parent->left = cur->left; } } 有两个子树: 选择 CC40.【C++ Cont】二叉搜索树和平衡二叉树 文章的这个方法: 用左子树的最大节点的值替换,再删除左子树最大节点 先找最大节点:

while (left_max->right) { left_max = left_max->right; } 循环结束时,left_max指向cur的左子树中的最大节点 删除节点的错误做法:让left_max和要删除的节点的key值交换,然后删除left_max指向的节点

//swap(cur->key,left_max->key); //erase(left_max); 交换后,left_max指向的节点会找不到的! 例如删除以下二叉搜索树的8:

8的左子树的最大节点是5,那么有:

正确做法:不能直接删除,交换后要借助left_max的父节点parent,而且parent的初始值为cur,不能为nullptr

Node* left_max = cur->left; Node* parent = cur; while (left_max->right) { parent = left_max; left_max = left_max->right; } swap(cur->key, left_max->key); if (parent->left==left_max) parent->left = left_max->left;//left_max->right为空,不可能有parent->left=left_max->left else parent->right = left_max->left; delete left_max;//交换过了,所以不能删除cur,要删除left_max return true; 如果parent的初始值为nullptr,那么这个特殊情况会出问题: 例如删除以下二叉搜索树的5,left_max指向3,cur指向5,parent为nullptr,则if (parent->left==left_max)为if ( nullptr ->left==left_max), 空指针无法访问会报错!

画图解释删除的if判断 一般情况 删除3:

解析:

特殊情况 1.删除5:

解析:

2.整个二叉树只有一个节点 3.整个二叉树只有两个节点

4.是空树 完整代码:

} } //cur为nullptr,没找到 return false; } priva 测试代码:

运行结果:

4.练习1: [LintCode]删除二叉查找树的节点 https://www.lintcode.com/problem/87/ 描述 给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。

如果树中没有相同值的节点，就不做任何处理。

你应该保证处理之后的树仍是二叉查找树。

样例 1： 输入：

value = 3 输出：

解释：

5 / \ 3 6 / \ 2 4 移去3，你可以返回: 5 / \ 2 6 \ 4 或 5 / \ 4 6 / 2 样例 2： 输入：

value = 4 输出：

解释：

5 / \ 3 6 / \ 2 4 移去4，你应该返回 5 / \ 3 6 / 2 代码 一定要考虑特殊情况!

* Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of the binary search tree. * @param value: Remove the node with given value. * @return: The root of the binary search tree after removal. */ TreeNode* removeNode(TreeNode *root, int value) { TreeNode* cur = root; TreeNode* parent = nullptr; while (cur) { if (cur == nullptr)//节点不存在,特殊情况 return root; if (cur->val > value) { parent = cur; cur = cur->left; } else if (cur->val < value) { parent = cur; cur = cur->right; } else //cur->val == value { if (cur->left == cur->right)//只有cur->left==cur->right==nullptr这一种情况 { if (parent==nullptr)//该二叉搜索树只有一个节点,特殊情况 { delete cur; return nullptr; } if (parent->left == cur) parent->left = nullptr; else parent->right = nullptr; delete cur; return root; } else if (cur->left && cur->right) { TreeNode* left_max = cur->left; TreeNode* parent = cur; while (left_max->right) { parent = left_max; left_max = left_max->right; } swap(cur->val, left_max->val); if (parent->left==left_max) parent->left = left_max->left; else parent->right = left_max->left; delete left_max; return root; } else { if (cur->left == nullptr) { if (cur == root)//parent==nullptr,特殊情况 { root = cur->right; delete cur; return root; } if (parent->right == cur) parent->right = cur->right; else parent->left = cur->right; } if (cur->right == nullptr) { if (cur == root)//parent==nullptr,特殊情况 { root = cur->left; delete cur; return root; } if (parent->right == cur) parent->right = cur->left; else parent->left = cur->left; } delete cur; return root; } } } return root;//cur为nullptr } }; 提交结果

6.练习2: [LintCode]在二叉查找树中插入节点 https://www.lintcode.com/problem/85/?_from=problem_tag&fromId=358 描述 给定一棵二叉查找树和一个新的树节点，将节点插入到树中。

你需要保证该树仍然是一棵二叉查找树。

样例 1： 输入：

node= 1 输出：

解释： 在空树中插入一个点，应该插入为根节点。

样例 2： 输入：

node = 6 输出：

解释：

挑战 能否不使用递归？

代码

提交结果

5.练习3: 使用二叉搜索树排序 https://leetcode.cn/problems/sort-an-array/description/ 给你一个整数数组

，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为

，并且空间复杂度尽可能小。

示例 1：

示例 2：

提示：

代码 将key换成pair,K表示存储的数据,第二个int表示该数字重复出现的次数

提交结果 算法没有问题,但是当数据量大,而且是二叉搜索树的极端情况时,插入节点的时间复杂度为

,容易超时,具体解决方法之后在讲AVL树和红黑树会提到

6.对比二叉搜索树和有序数组 有序数组二分查找速度快,但是插入和删除元素的效率低 一般情况下的二叉搜索树的增删查改的速度都很快,但极端情况效率低 极端情况: