【数据结构二叉树】先序层序建立、递归非递归遍历层序遍历、树高、镜面、对称、子树、合并、目标路径、带权路径和等等

二叉树

前言：这篇博客需要你对于二叉树有大致的了解，并且对于递归有一定的理解，懂得先序中序后序层次是啥等等，因为在这篇博客我不会对这一些概念进行讲解，我只会将我写的我看见的比较好比较简洁的代码块截下来，并不会对它进行进行过多的讲解，所以如果选择了这一篇博客，就应该做好理解透彻的准备！

1. 二叉树的建立（递归创建，结构体指针形式）

先来给出结构体：

struct Node
{char data;Node* leftchild = nullptr;Node* rightchild = nullptr;
};

1.1. 先序建立

#include<iostream>
#include<string>
using namespace std;
struct Node
{char a;Node* leftchild = nullptr;Node* rightchild = nullptr;
};
class BuildTree
{
public:Node* gen;int i = 0;//遍历arrBuildTree() { gen = nullptr; }void setTree(string arr){gen = new Node;CreateBiTree(gen, arr);return;}// 核心代码void CreateBiTree(Node*& root, string strTree) //先序遍历构建二叉树{char ch;ch = strTree[i++];if (ch == '#'){root = NULL;}else{root = new Node();root->a = ch;CreateBiTree(root->leftchild, strTree);CreateBiTree(root->rightchild, strTree);}return;}
};
int main()
{int n;cin >> n;while (n--){BuildTree* bt = new BuildTree;string arr;cin >> arr;bt->setTree(arr);delete bt;}
}

1.2. 层序建立

#include <iostream>
#include <queue>
#include <string>
using namespace std;struct Node {char data;Node* leftchild;Node* rightchild;
};void pre_view(Node* root)
{if (root != nullptr){cout << root->data << ' ';pre_view(root->leftchild);pre_view(root->rightchild);}return;
}// 层序建立
void CreateBiTree(Node*& root, string strTree) {if (strTree.empty()) {root = nullptr;return;}queue<Node*> nodeQueue;int i = 0;root = new Node();root->data = strTree[i++];nodeQueue.push(root);while (!nodeQueue.empty()) {Node* current = nodeQueue.front();nodeQueue.pop();if (i < strTree.length() && strTree[i] != '#') {current->leftchild = new Node();current->leftchild->data = strTree[i];nodeQueue.push(current->leftchild);}i++;if (i < strTree.length() && strTree[i] != '#') {current->rightchild = new Node();current->rightchild->data = strTree[i];nodeQueue.push(current->rightchild);}i++;}
}int main() {string strTree = "122#3#3";Node* root = nullptr;CreateBiTree(root, strTree);// 先序遍历查看结果pre_view(root);return 0;
}

2. 递归遍历(结构体指针)

2.1. 先序遍历

void pre_send(Node* root)
{if (root != NULL){cout << (root->data);pre_send(root->leftchild);pre_send(root->rightchild);}return;
}

2.2. 中序遍历

void in_sned(Node* root)
{if (root != NULL){in_sned(root->leftchild);cout << (root->data);in_sned(root->rightchild);}return;
}

2.3. 后序遍历

void post_send(Node* root)
{if (root != NULL){post_send(root->leftchild);post_send(root->rightchild);cout << (root->data);}return;
}

3. 非递归遍历(结构体指针)

首先给出结构体：

struct Node
{int a;Node* Leftchild = nullptr;Node* Rightchild = nullptr;
}

3.1. 层次遍历

void levelorder(Node* gen)
{queue<Node*>q;q.push(gen);while (!q.empty()){Node* now = q.front();q.pop();if (now == nullptr)continue;cout << now->a;if (now->Leftchild != nullptr)q.push(now->Leftchild);if (now->Rightchild != nullptr)q.push(now->Rightchild);}
}

3.2. 后序遍历(非递归)

void postRead(Node* gen)
{stack<Node*>s;Node* root = gen, * check = nullptr;while (root != nullptr || !s.empty()){if (root != nullptr)//一直向左走{s.push(root);root = root->Leftchild;}else{root = s.top();//右节点存在且未访问if (root->Rightchild != nullptr && root->Rightchild != check){root = root->Rightchild;s.push(root);root = root->Leftchild;}else{s.pop();cout << root->a;check = root;root = nullptr;}}}
}

4. 求树的高度

int getHeight(Node* root)
{if (root == nullptr)return 0;int leftdeep = getHeight(root->Leftchild);int rightdeep = getHeight(root->Rightchild);int deep = 1 + (leftdeep > rightdeep ? leftdeep : rightdeep);return deep;
}

5. 中后序遍历构建

这个部分是我在做题的时候看到的，感觉搞懂这一块之后会对前中后序有更好的理解，这一道题就是：知道后序的规律！题目名字为：二叉树的中后序遍历构建及求叶子，可以自己搜搜看。

#include<iostream>
#include<cstring>
using namespace std;
class Tree
{
public:int* mid;int* last;int min = 10000000;Tree(int t){mid = new int[t + 5];last = new int[t + 5];for (int i = 0; i < t; i++){cin >> mid[i];}for (int i = 0; i < t; i++){cin >> last[i];}}~Tree(){delete mid, last;}int get_min(){return min;}void BuildTree(int mid_l, int mid_r, int last_l, int last_r){if (mid_l == mid_r){if (mid[mid_l] <= min)min = mid[mid_l];return;}for (int i = mid_l; i <= mid_r; i++){if (mid[i] == last[last_r]){BuildTree(mid_l, i - 1, last_l, last_l + i - mid_l - 1);BuildTree(i + 1, mid_r, last_l + i - mid_l, last_r - 1);}}}
};
int main()
{int n;cin >> n;while (n--){int t;cin >> t;Tree* tree = new Tree(t);tree->BuildTree(0, t - 1, 0, t - 1);cout << tree->get_min() << endl;delete tree;}return 0;
}

6. 二叉树镜面翻转

void Mirror_inversion(Node* p)
{if (p != NULL){Mirror_inversion(p->Leftchild);Mirror_inversion(p->Rightchild);swap(p->Leftchild, p->Rightchild);}
}

7. 对称二叉树

bool judge(Node* root_1, Node* root_2)
{if (root_1 == nullptr && root_2 == nullptr){return true;}else if (root_1 == nullptr || root_2 == nullptr){return false;}else if (root_1->data != root_2->data){return false;}return judge(root_1->leftchild, root_2->rightchild) && judge(root_1->rightchild, root_2->leftchild);
}bool isSymmetric(Node* root)
{return judge(root->leftchild, root->rightchild);
}

8. 输出所有目标路径

void DFS_target(Node* node, int targetSum, vector<int>& path, vector<vector<int>>& result) {if (node == nullptr) {return;}path.push_back(node->data);if (node->leftchild == nullptr && node->rightchild == nullptr) {if (targetSum == node->data) {result.push_back(path);}}else {DFS_target(node->leftchild, targetSum - node->data, path, result);DFS_target(node->rightchild, targetSum - node->data, path, result);}path.pop_back();return;
}

9. 判断是否为子树

bool isSameTree(Node* t1, Node* t2) {// 考虑到后面子叶节点的左右节点，如果都为空就会返回Trueif (!t1 && !t2) {return true;}// 如果有一个节点有左右节点，而另一个节点没有的话就会返回false，而都有不会进入，都没有在上面会返回Trueif (!t1 || !t2) {return false;}return (t1->data == t2->data) && isSameTree(t1->leftchild, t2->leftchild) && isSameTree(t1->rightchild, t2->rightchild);
}// 判断tree1是否包含tree2的子树
bool isSubtree(Node* tree1, Node* tree2) {if (!tree1) {return false;}// tree1不空就开始考虑if (isSameTree(tree1, tree2)) {return true;}// 每一个节点向下进行考虑，如果有一个是符合的就返回Truereturn isSubtree(tree1->leftchild, tree2) || isSubtree(tree1->rightchild, tree2);
}

10. 合并二叉树

void addWith(Node*& root_1, Node* root_2)
{if (root_1 == nullptr && root_2 != nullptr){root_1 = new Node;root_1->data = root_2->data;root_1->leftchild = root_2->leftchild; // Handle left childroot_1->rightchild = root_2->rightchild; // Handle right childreturn;}if (root_2 == nullptr){return;}root_1->data += root_2->data;addWith(root_1->leftchild, root_2->leftchild);addWith(root_1->rightchild, root_2->rightchild);
}

11. 带权路径和

void findDeepTree(Node* root, int* data, int dis)
{if (root == nullptr || index == n){return;}if (root->leftchild == nullptr && root->rightchild == nullptr){result = result + dis * data[index++];return;}if (root->leftchild != nullptr)findDeepTree(root->leftchild, data, dis + 1);if (root->rightchild != nullptr)findDeepTree(root->rightchild, data, dis + 1);return;
}