目录
1.知识回顾
参见CC40.【C++ Cont】二叉搜索树和平衡二叉树文章复习基础知识
2.练习:在二叉搜索树中查找指定值
https://www.lintcode.com/problem/1524/?_from=problem_tag&fromId=358
给定一颗二叉搜索树和
value.返回这棵树中值等于
value的节点. 如果不存在这样的节点, 返回null.样例 1:
输入: value = 2 4 / \ 2 7 / \ 1 3 输出: 节点 2样例 2:
输入: value = 5 4 / \ 2 7 / \ 1 3 输出: null
分析:
比较要找的值和根节点的大小关系,沿着二叉搜索树的边遍历就行
代码:
/**
* 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 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_val<val)
root=root->right;
else
root=root->left;
}
return nullptr;
}
};提交结果:
3.模拟实现二叉搜索树
框架
构建二叉搜索树类和节点类
template<class K>
class Node
{
public:
Node<K>* left;
Node<K>* right;
K key;
};
template<class K>
class Binary_Search_Tree
{
typedef Binary_Search_Tree<K> Node;
public:
//......
private:
Node* root;
};初始化
二叉搜索树的构造函数
Binary_Search_Tree()
:root(nullptr)
{ }节点的构造函数
Node(const K& val)
:left(nullptr)
,right(nullptr)
,key(val)
{ }插入节点,不能插入相同的key
首先要讨论是否为空树,如果为空是无法遍历树的
bool insert(const K& val)
{
//分根节点是否为空讨论
if (root)
{
//......
}
else
{
root = new Node<K>(val);
return true;
}
}当树不为空时,寻找合适的位置,让cur指针遍历
Node<K>* cur = root;
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的根节点,即双指针:
Node<K>* cur = root;
//一开始cur指向树的根节点时,cur是没有父节点的,可以理解为nullptr,当然值也可以不设置
Node<K>* 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
cur = new Node<K>(val);
//此时不可能有parent->val == val,前面排除过了
if (parent->key < val)
parent->right = cur;
else
parent->left = cur;完整代码:
bool insert(const K& val)
{
//分根节点是否为空讨论
if (root)
{
Node<K>* cur = root;
Node<K>* 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<K>(val);
//此时不可能有parent->val == val,前面排除过了
if (parent->key < val)
parent->right = cur;
else
parent->left = cur;
}
else
{
root = new Node<K>(val);
}
return true;
}中序遍历
中序遍历的复习参见106.【C语言】数据结构之二叉树的三种递归遍历方式文章,该文章提供的代码段为:
void InOrder(BTNode* root)
{
//先判断是否为空树(叶节点的左节点和右节点均为空树)
if (root == NULL)
{
printf("NULL ");
return;
}
//按左子树-->根-->右子树的顺序遍历
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}但不能直接当做成员函数print_inoder,因为root是私有变量,调用print_inoder函数是不能传参的,因此需要将InOrder写成子函数,然后print_inoder调用InOrder
完整代码:
void print_inoder()
{
InOrder(root);
}
private:
void InOrder(Node<K>* root)
{
//先判断是否为空树(叶节点的左节点和右节点均为空树)
if (root == NULL)
return;
//按左子树-->根-->右子树的顺序遍历
InOrder(root->left);
cout<< root->key<<" ";
InOrder(root->right);
}
Node<K>* root;测试代码:
#include "BinarySearchTree.h"
int main()
{
Binary_Search_Tree<int> 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;
}运行结果:中序遍历是有序的
查找节点
借鉴插入节点的部分代码:
bool find(const K& val)
{
Node<K>* 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;
}测试代码:
#include "BinarySearchTree.h"
int main()
{
Binary_Search_Tree<int> 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<K>* cur = root;
//一开始cur指向树的根节点时,cur是没有父节点的,可以理解为nullptr,当然值也可以不设置
Node<K>* 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
if (cur->left == cur->right)//只有cur->left==cur->right==nullptr这一种情况
{
if (parent->left == cur)
parent->left = nullptr;
else
parent->right = nullptr;
}
//......
delete cur;有一个子树: 要分类讨论是左子树还是右子树
例如要删除3:
循环结束后parent和cur的指向为:
直接将parent->right设置为cur->right
//让删除的节点的左子树或右子树直接替代其位置,需要parent
if (cur->left == nullptr)
{
if (parent->right == cur)
parent->right = cur->right;
else
parent->left = cur->right;
}这样做的前提是parent不为空,如果cur==root是需要单独操作的!
else//有一棵子树
{
//让删除的节点的左子树或右子树直接替代其位置,需要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】二叉搜索树和平衡二叉树文章的这个方法: 用左子树的最大节点的值替换,再删除左子树最大节点
先找最大节点:
Node<K>* left_max = cur->left;
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<K>* left_max = cur->left;
Node<K>* 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.是空树
完整代码:
bool erase(const K& val)
{
//先找节点
Node<K>* cur = root;
//一开始cur指向树的根节点时,cur是没有父节点的,可以理解为nullptr,当然值也可以不设置
Node<K>* 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 // (cur->key == val)
{
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 true;
}
else if (cur->left && cur->right)//有两棵子树
{
//用左子树的最大节点的值替换,再删除左子树最大节点
Node<K>* left_max = cur->left;
Node<K>* 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;
}
else//有一棵子树
{
//让删除的节点的左子树或右子树直接替代其位置,需要parent
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 true;
}
}
}
//cur为nullptr,没找到
return false;
}
priva测试代码:
#include "BinarySearchTree.h"
int main()
{
Binary_Search_Tree<int> bst;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
bst.insert(e);
}
bst.print_inoder();
bst.erase(4);
bst.print_inoder();
bst.erase(6);
bst.print_inoder();
bst.erase(7);
bst.print_inoder();
bst.erase(3);
bst.print_inoder();
return 0;
}
运行结果:
4.练习1: [LintCode]删除二叉查找树的节点
https://www.lintcode.com/problem/87/
描述
给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。
样例 1：
输入：
Tree = {5,3,6,2,4} value = 3输出：
{5,2,6,#,4} 或 {5,4,6,2}解释：
给定了以下二叉搜索树: 5 / \ 3 6 / \ 2 4 移去3，你可以返回: 5 / \ 2 6 \ 4 或 5 / \ 4 6 / 2样例 2：
输入：
Tree = {5,3,6,2,4} value = 4输出：
{5,3,6,2}解释：
给定了以下二叉搜索树: 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：
输入：
tree = {} node= 1输出：
{1}解释：
在空树中插入一个点，应该插入为根节点。
样例 2：
输入：
tree = {2,1,4,#,#,3} node = 6输出：
{2,1,4,#,#,3,6}解释：
挑战
能否不使用递归？
代码
/**
* 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 node: insert this node into the binary search tree
* @return: The root of the new binary search tree.
*/
TreeNode * insertNode(TreeNode * root, TreeNode * node)
{
//分根节点是否为空讨论
if (root)
{
TreeNode * cur = root;
TreeNode * parent = nullptr;//一开始cur指向树的根节点时,cur是没有父节点的
while (cur)
{
if (cur->val > node->val)
{
parent = cur;
cur = cur->left;
}
else if (cur->val < node->val)
{
parent = cur;
cur = cur->right;
}
else
{
return root;
}
}
if (parent->val < node->val)
parent->right = node;
else
parent->left = node;
}
else
{
root = node;
}
return root;
}
};
提交结果
5.练习3: 使用二叉搜索树排序
https://leetcode.cn/problems/sort-an-array/description/
给你一个整数数组
nums，请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为
O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5] 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 解释：请注意，nums 的值不一定唯一。提示：
1 <= nums.length <= 5 * 10^4-5 * 10^4 <= nums[i] <= 5 * 10^4
代码
将key换成pair<K,int>,K表示存储的数据,第二个int表示该数字重复出现的次数
template<class K>
class Binary_Search_Tree;//前向声明
template<class K>
class Node
{
public:
Node(const K& val)
:left(nullptr)
, right(nullptr)
, key(val,1)
{
}
Node<K>* left;
Node<K>* right;
pair<K,int> key;
};
template<class K>
class Binary_Search_Tree
{
public:
Binary_Search_Tree()
:root(nullptr)
{}
void insert(const K& val)
{
//分根节点是否为空讨论
if (root)
{
Node<K>* cur = root;
Node<K>* parent = nullptr;//一开始cur指向树的根节点时,cur是没有父节点的
while (cur)
{
if ((cur->key).first > val)
{
parent = cur;
cur = cur->left;
}
else if ((cur->key).first < val)
{
parent = cur;
cur = cur->right;
}
else//(cur->key).first == val,不能插入相同数字
{
cur->key.second++;
return;
}
}
cur = new Node<K>(val);
if ((parent->key).first < val)
parent->right = cur;
else
parent->left = cur;
}
else
{
root = new Node<K>(val);
}
}
void wirte_vector(vector<K>& v)
{
InOrder(root,v);
}
private:
void InOrder(Node<K>* root,vector<K>& v)
{
//先判断是否为空树(叶节点的左节点和右节点均为空树)
if (root == NULL)
return;
//按左子树-->根-->右子树的顺序遍历
InOrder(root->left,v);
while ((root->key).second--)
v.push_back((root->key).first);
InOrder(root->right,v);
}
Node<K>* root;
};
class Solution {
public:
vector<int> sortArray(vector<int>& nums)
{
Binary_Search_Tree<int> bst;
vector<int> ret;
for (auto a:nums)
bst.insert(a);
bst.wirte_vector(ret);
return ret;
}
};
提交结果
算法没有问题,但是当数据量大,而且是二叉搜索树的极端情况时,插入节点的时间复杂度为,容易超时,具体解决方法之后在讲AVL树和红黑树会提到
6.对比二叉搜索树和有序数组
有序数组二分查找速度快,但是插入和删除元素的效率低
一般情况下的二叉搜索树的增删查改的速度都很快,但极端情况效率低
极端情况:
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
