BST树区间元素搜索问题
比如说，寻找10-70之间的所有元素
方法1： 遍历1遍，符合的打印出来。但是效率不高。
方法2：
利用中序遍历的升序的特点。
//求满足区间的元素值[i, j]
void findValues(vector<T>& vec, int i, int j)
{
findValues(root_, vec, i, j);
}
//求满足区间的元素值[i, j]实现
void findValues(Node* node, vector<T>& vec, int i, int j)
{
if (node != nullptr)
{
//在当前节点的左子树中搜索 LVR的方式，中序遍历
if (node->data_ > i)//比i小就不用去左子树搜索了
{
findValues(node->left_, vec, i, j);//执行L
}
if (node->data_ >= i && node->data_ <= j)//执行V
{
vec.push_back(node->data_);//存储满足区间元素的值
}
//在当前节点的右子树中搜索
if (node->data_ < j)//比j大就不用去右子树搜索了
{
findValues(node->right_, vec, i, j);//执行R
}
}
}
判断一棵树是不是BST树
要考虑到上图这种情况来实现代码
利用BST树的中序遍历是从小到大升序的思想
//判断二叉树是否是BST树
bool isBSTree()
{
Node* pre = nullptr;//用来记录中序遍历前一个节点的值，一直要更新的
return isBSTree(root_, pre);
}
//判断二叉树是否是BST树的实现 利用BST树中序遍历是一个升序的特点
bool isBSTree(Node* node, Node*& pre)
{
if (node == nullptr)
{
return true;
}
if (!isBSTree(node->left_, pre))//L主要判断使递归结束的条件
{
return false;
}
//V
if (pre != nullptr)
{
if (comp_(node->data_, pre->data_))
//当前节点的值小于前一个节点的值。主要判断使递归结束的条件
{
return false;
}
}
pre = node;//更新中序遍历的前驱节点
return isBSTree(node->right_, pre);//R
}
判断二叉树子树问题
判断下面这个小树是不是上面这棵大树的子树
先在大树中找到这个小树的根节点67
然后大树和小树同时往左走往右走遍历
遍历到的值必须是相同的
大树里的可以多，但不能少。
//判断子树问题
bool isChildTree(BSTree<T, Comp>& child)
{
// 在当前二叉树上找child的根节点
if (child.root_ == nullptr)
{
return true;
}
Node* cur = root_;
while (cur != nullptr)
{
if (cur->data_ == child.root_->data_)//树的节点与子树的根节点值相等
{
break;
}
else if (comp_(cur->data_, child.root_->data_))//当前节点的值小于子树的根节点的值
{
cur = cur->right_;
}
else//当前节点的值大于子树的根节点的值
{
cur = cur->left_;
}
}
if (cur == nullptr)
{
return false;//没有找到子树的根，不匹配
}
return isChildTree(cur, child.root_);
}
//判断子树问题实现
bool isChildTree(Node* father, Node* child)
{
if (father == nullptr && child == nullptr)
{
return true;
}
if (father == nullptr)//子树里面有的节点，当前二叉树没有
{
return false;
}
if (child == nullptr)
{
return true;
}
//判断值不相同
if (father->data_ != child->data_)// V 对应的值不相同
{
return false;
}
return isChildTree(father->left_, child->left_)// L 左右孩子同时进行判断
&& isChildTree(father->right_, child->right_);// R
}
求LCA最近公共祖先节点
比如说24和67，最近公共祖先节点就是58，
32和64，最近公共祖先节点就是58
5和41的最近公共祖先节点就是24
62和64的最近公共祖先节点就是62
怎么判断5和41的最近公共祖先节点是24，而不是58？
我们看，5和41都比58小，说明都在58的左子树，58就肯定不是它们的最近公共祖先节点。最近公共祖先节点肯定是大于一个数而小于另一个数。
搜索的时候值等于要比较的节点值，就是在一条分枝上。
//最近公共祖先节点
int getLCA(int val1, int val2)
{
Node* node = getLCA(root_, val1, val2);
if (node == nullptr)//没找到
{
throw "no LCA!";
}
else
{
return node->data_;
}
}
//最近公共祖先节点实现
Node* getLCA(Node* node, int val1, int val2)
{
if (node == nullptr)
{
return nullptr;
}
if (comp_(node->data_, val1) && comp_(node->data_, val2))//当前节点的值小于val1和val2
{
return getLCA(node->right_, val1, val2);
}
else if (comp_(val1, node->data_) && comp_(val2, node->data_))//当前节点的值大于val1和val2
{
return getLCA(node->left_, val1, val2);
}
else//一个大于一个小于。就是最近公共祖先节点。
{
return node;
}
}
二叉树镜像翻转问题
相当于有一面镜子
翻转。
78就是在最左边
0就是在最右边
相当于根节点进行遍历，把左右的节点交换就可以了。
//镜像翻转
void mirror01()
{
mirror01(root_);
}
//镜像翻转
void mirror01(Node* node)
{
if (node == nullptr)
return;
//前序遍历
//V
Node* tmp = node->left_;
node->left_ = node->right_;
node->right_ = tmp;//交换节点
mirror01(node->left_);//L操作
mirror01(node->right_);//R操作
}
二叉树的镜像对称
就是在根节点放一面镜子
看左子树和右子树是不是对称，就是左右对应节点的值相等不相等。
//镜像对称
bool mirror02()
{
if (root_ == nullptr)
return true;
return mirror02(root_->left_, root_->right_);
}
//镜像对称
bool mirror02(Node* node1, Node* node2)
{
if (node1 == nullptr && node2 == nullptr)
{
return true;
}
if (node1 == nullptr || node2 == nullptr)
{
return false;
}
if (node1->data_ != node2->data_)
{
return false;
}
return mirror02(node1->left_, node2->right_)
&& mirror02(node1->right_, node2->left_);
}
已知BST树的前序遍历和中序遍历，重建BST树
前序遍历是VLR，中序遍历是LVR，
所以说
前序遍历的第一个数字58就是根节点！！！
但是58的左子树和右子树都有哪些节点？
中序遍历的58的左边数字就是根节点的左子树，58的右边数字就是根节点的右子树
我们拿前序遍历的第一个数字，58，也就是根节点。
然后拿这个数值去中序遍历里面找。第k个位置。
m到k-1就是根节点58的右子树的节点
根节点的左子树的节点个数：k-m
那58的左子树的前序遍历是什么呢？
58的左子树的前序遍历的下标就是从i+1开始到 i+（k-m）
那它们的根就是下标为i+1的元素，即24
然后拿24在中序遍历里找。
24的左边就是它的左子树。就是 0,5
右子树就是34,41
创建根的右子树就是从k+1到n
//重建二叉树
void rebuild(int pre[], int i, int j, int in[], int m, int n)//前序，中序，起始，末尾下标
{
root_ = _rebuild(pre, i, j, in, m, n);
}
//重建二叉树递归实现
Node* _rebuild(int pre[], int i, int j, int in[], int m, int n)
{
if (i > j || m > n)//已经遍历完了
{
return nullptr;
}
//创建当前子树的根节点
Node* node = new Node(pre[i]);//拿前序的第一个数字创建子树根节点 V
for (int k = m; k <= n; ++k)
{
if (pre[i] == in[k])//在中序遍历中找子树根节点的下标k
{
node->left_ = _rebuild(pre, i + 1, i + (k - m), in, m, k - 1);// L
node->right_ = _rebuild(pre, i + (k - m) + 1, j, in, k + 1, n);// R
return node;
}
}
return node;
}
判断一棵BST树是否是平衡树
任意节点的左右子树的高度差不超过1（0,1，-1）
在回溯的时候检测，比较好。
LRV
//判断平衡树
bool isBalance()
{
int l = 0;
bool flag = true;
isBalance02(root_, l, flag);
return flag;
}
//判断平衡树 效率比较低，遍历的次数太多了
bool isBalance(Node* node)
{
if (node == nullptr)
return true;
if (!isBalance(node->left_))//L
return false;
if (!isBalance(node->right_))//R
return false;
int left = high(node->left_);
int right = high(node->right_);
return abs(left - right) <= 1;//V
}
//判断平衡树 效率高 递归过程中，记录了节点的高度值 ，返回节点高度值
int isBalance02(Node* node, int l, bool& flag)
{
if (node == nullptr)
{
return l;
}
int left = isBalance02(node->left_, l + 1, flag);//L
if (!flag)
return left;
int right = isBalance02(node->right_, l + 1, flag);//R
if (!flag)
return right;
//V
if (abs(left - right) > 1)//节点失衡了
{
flag = false;
}
return max(left, right);
}
求中序遍历倒数第k个节点
VLR
我们用VRL就是正数第k个
//求中序倒数第K个节点
int getVal(int k)
{
Node* node = getVal(root_, k);
if (node == nullptr)
{
string err = "no No.";
err += k;
throw err;
}
else
{
return node->data_;
}
}
//求中序倒数第K个节点
int i = 1;
Node* getVal(Node* node, int k)
{
if (node == nullptr)
return nullptr;
Node* left = getVal(node->right_, k); // R
if (left != nullptr)
return left;
//V
if (i++ == k)//在VRL的顺序下，找到正数第k个元素
{
return node;
}
return getVal(node->left_, k);//L
}
BST树的析构函数
//层序遍历思想释放BST树所有节点资源
~BSTree()//析构函数
{
if (root_ != nullptr)
{
queue<Node*> s;
s.push(root_);//根节点入队
while (!s.empty())
{
Node* front = s.front();//获取队头
s.pop();//出队
if (front->left_ != nullptr)
{
s.push(front->left_);
}
if (front->right_ != nullptr)
{
s.push(front->right_);
}
delete front;
}
}
}