为实习准备的数据结构（4）-- 二叉树
前言
半年前，种过一次树，有不少朋友喜欢。但是接下来我又要重新种树了，因为我发现，有瑕疵（我忘得差不多了）。不过可以放心，前面那篇我不会删，毕竟大家比较喜欢。
能不多说话就不多说话，需要看概念的话可以去前一篇：种树[1]
二叉树
二叉树的创建
class TreeNode {
private:
int val; //这里的数据类型按需取
TreeNode* left;
TreeNode* right;
public:
TreeNode(int x) :val(x), left(NULL), right(NULL){}
int get_val() {
return this->val;
}
TreeNode* getleft() {
return this->left;
}
TreeNode* getright() {
return this->right;
}
void set_left(TreeNode* node) {
this->left = node;
}
void set_right(TreeNode* node) {
this->right = node;
}
};
二叉树的前序遍历
以此图为例：==先访问根结点，然后再访问左子树，最后访问右子树。==
void PreOrderTraverse(TreeNode* root) {
if (NULL == root) {
return;
}
cout << root->get_val() << endl;
PreOrderTraverse(root->getleft());
PreOrderTraverse(root->getright());
}
打印信息：ABDECFG
二叉树的中序遍历
==先访问左子树，中间访问根节点，最后访问右子树。==
void MidOrderTraverse(TreeNode* root) {
if (NULL == root) {
return;
}
MidOrderTraverse(root->getleft());
cout << root->get_val() << endl;
MidOrderTraverse(root->getright());
}
打印信息：DBEAFCG
二叉树的后序遍历
==先访问左子树，再访问右子树，最后访问根节点。==
void LastOrderTraverse(TreeNode* root){
if(NULL == root)
return;
LastOrderTraverse(root->left);
LastOrderTraverse(root->right);
cout<<root->val;
}
打印顺序：DEBFCA
已知前、中序遍历，还原二叉树
==特别标注：如果二叉树中有相同值元素的存在，那么有极大概率还原失败，下面中、后序遍历也是==
给了中序那就好办了
一：看中序排列中的根节点位置在哪里，根节点前面都属于根的左子树及其后代，后面你懂得。
二：将中序序列分两段：（D、B、E）和（F、C、G）
三：明眼人一看就知道根节点左子树的“根节点”是：B
别问我为啥，问就是看前序序列的第二位
四：重复二三，直到根节点左子树排出来为止
五：同上，排出右子树
具体思路：
对于任意一颗树而言，前序遍历的形式总是 [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] 即根节点总是前序遍历中的第一个节点。
而中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
细节
在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。我们可以考虑使用哈希映射（HashMap）来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要 O(1) 的时间对根节点进行定位了。
下面的代码给出了详细的注释。
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
> 作者：LeetCode-Solution
> 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h < nh<n，所以总空间复杂度为 O(n)。
已知后序、中序遍历结果，还原二叉树
这个LeetCode上没找到，我模仿着写一个。
//一、二步同上
//其实第三步原理是一样的，不过我们的脑子习惯了从前到后，所以，让我帮你们转个弯。
//像对中序分割一样，将后序序列也分割了。
//从中序排列的分割中我们知道根节点的右子树有哪些成员，所以后序序列这样分：
//（H I D J K E B）（L F G C）
//现在就很明显可以看出根节点左子树的“根节点”是谁了吧
//重复以上步骤
具体思路：
对于任意一颗树而言，后序遍历的形式总是 [ [左子树的前序遍历结果], [右子树的前序遍历结果],根节点 ] 即根节点总是后序遍历中的最后一个节点。
而中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的后序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到后序遍历的结果中，对上述形式中的所有左右括号进行定位。
这样以来，我们就知道了左子树的后序遍历和中序遍历结果，以及右子树的后序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* myBuildTree(const vector<int>& lastorder, const vector<int>& inorder, int lastorder_left, int lastorder_right, int inorder_left, int inorder_right) {
if (lastorder_left > lastorder_right) {
return nullptr;
}
// 后序遍历中的最后一个节点就是根节点
int lastorder_root = lastorder_right;
// 在中序遍历中定位根节点
int inorder_root = index[lastorder[lastorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(lastorder[lastorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 后序遍历中「从 左边界开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = myBuildTree(lastorder, inorder, lastorder_left, lastorder_left + size_left_subtree-1, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 后序遍历中「从 左边界+左子树节点数目 开始到 右边界-1 」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = myBuildTree(lastorder, inorder, lastorder_left + size_left_subtree, lastorder_right-1, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
二叉树的层序遍历
所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下：
实现步骤：
1.创建队列，存储每一层的结点；
2.使用循环从队列中弹出一个结点：
2.1获取当前结点的key；
2.2如果当前结点的左子结点不为空，则把左子结点放入到队列中
2.3如果当前结点的右子结点不为空，则把右子结点放入到队列中
代码实现：
#include<queue>
#include<iostream>
using namespace std;
void LevelOrder(Node *root) {
if (root == NULL)
return;
queue<Node *> q;
// 启动
q.push(root);
while (!q.empty()) {
Node *front = q.front();
q.pop();
cout<<front->value;
if (front->left != NULL)
q.push(front->left);
if (front->right != NULL)
q.push(front->right);
}
cout<<endl;
}
二叉搜索树
所谓二叉搜索树，可提供对数时间的元素插入和访问。二叉搜索树的节点放置规则是：任何节点的键值一定大于去其左子树中的每一个节点的键值，并小于其右子树的每一个节点的键值。
所以在二叉树中找到最大值和最小值是很简单的，比较麻烦的是元素的插入和移除。插入新元素时，从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到尾端，即为插入点。移除旧元素时，如果它是叶节点，直接拿走就是了；如果它有一个节点，那就把那个节点补上去；如果它有两个节点，那就把它右节点的最小后代节点补上去。
构造二叉搜索树
现有序列：A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根据此序列构造二叉搜索树过程如下：
（1）i = 0，A[0] = 61，节点61作为根节点；（2）i = 1，A[1] = 87，87 > 61，且节点61右孩子为空，故81为61节点的右孩子；（3）i = 2，A[2] = 59，59 < 61，且节点61左孩子为空，故59为61节点的左孩子；（4）i = 3，A[3] = 47，47 < 59，且节点59左孩子为空，故47为59节点的左孩子；（5）i = 4，A[4] = 35，35 < 47，且节点47左孩子为空，故35为47节点的左孩子；（6）i = 5，A[5] = 73，73 < 87，且节点87左孩子为空，故73为87节点的左孩子；（7）i = 6，A[6] = 51，47 < 51，且节点47右孩子为空，故51为47节点的右孩子；（8）i = 7，A[7] = 98，98 < 87，且节点87右孩子为空，故98为87节点的右孩子；（9）i = 8，A[8] = 93，93 < 98，且节点98左孩子为空，故93为98节点的左孩子；
创建完毕后如图中的二叉搜索树：
代码实现：
#include<vector>
#include<iostream>
using namespace std;
class SerchTree{
private:
TreeNode* root;
public:
SerchTree();
//插入节点
void Insert_Node(TreeNode* root,int val){
if(NULL == root)
root = new TreeNode(val);
else{
if(val<root->val)
Insert_Node(root->left,val);
else{ //一样大就往左走吧
Insert_Node(root->right,val);
}
}
}
//从数组中构造二叉搜索树
void Create_SerchTree(vector<int>& vec){
int sz = vec.size();
for(int i = 0;i<sz;i++){
Insert_Node(root,vec[i]);
}
}
//搜索某个节点是否存在
bool SerchNode(TreeNode* root,int val){
if(NULL == root)
return false;
if(val<root->val)
return SerchNode(root->left,val);
else if(val>root->val)
return SerchNode(root->right)
else
return ture;
}
//删除节点
void DelNode(TreeNode* node){
TreeNode* temp;
if(NULL == node->right){ //如果右子节点为空
temp = node;
node = node->left;
delete temp;
}
else{ //如果右子节点不空
temp = node;
while(NULL != temp->left){
temp = temp->left;
}
node->val = temp->val;
delete temp;
}
}
//删除某个节点
void DelSerchNode(TreeNode* root,int val){
if(NULL == root)
return;
if(val<root->val)
return DelSerchNode(root->left,val);
else if(val>root->val)
return DelSerchNode(root->right)
else
DelNode(root);
}
//计算二叉树的最大深度
int maxDepth(Node x) { //1.如果根结点为空，则最大深度为0；
if (x == null)
return 0;
int max = 0;
int maxL = 0;
int maxR = 0;
//2.计算左子树的最大深度；
if (x.left != null)
maxL = maxDepth(x.left);
//3.计算右子树的最大深度；
if (x.right != null)
maxR = maxDepth(x.right);
//4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
max = maxL > maxR ? maxL + 1 : maxR + 1; return max;
}
}
二叉树的其他操作
复制二叉树
这里需要在前面加上个函数：
void set_val(int val) {
this->val = val;
}
然后开始写，我们将后序遍历进行一个改装：
TreeNode* TreeCopy(TreeNode* root) {
if (root) {
TreeNode* temp = new TreeNode();
temp->set_left(TreeCopy(root->getleft()));
temp->set_right(TreeCopy(root->getright()));
temp->set_val(root->get_val());
return temp;
}
return NULL;
}
得到最终结果。
判断两个二叉树相等
这也是之前在LeetCode上做过的一道题了，这里我们也对后序遍历进行一次改写。
判断二叉树相等的几个要素：
1、二叉树结构相等
2、二叉树相对位置的值相等
所以产生代码如下：
bool is_equal_trees(TreeNode* a, TreeNode* b) {
return (!a && !b) || ((a && b) && (a->get_val() == b->get_val()) && is_equal_trees(a->getleft(), b->getleft()) && is_equal_trees(a->getright(), b->getright()));
}
在这里，我深刻的又体会到不要复制粘贴，尽管是自己的代码
树的东西太多啦，初步估计要整理个四五篇吧。
所以，这篇就先打个头阵。
References
[1] 种树: https://lion-wu.blog.csdn.net/article/details/107280503