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

二叉树

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

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

先来给出结构体：

struct Node
{
	char data;
	Node* leftchild = nullptr;
	Node* rightchild = nullptr;
};
1
2
3
4
5
6

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;//遍历arr
	BuildTree() { 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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

2.1. 先序遍历

void pre_send(Node* root)
{
    if (root != NULL)
    {
        cout << (root->data);
        pre_send(root->leftchild);
        pre_send(root->rightchild);
    }
    return;
}
1
2
3
4
5
6
7
8
9
10

2.2. 中序遍历

void in_sned(Node* root)
{
    if (root != NULL)
    {
        in_sned(root->leftchild);
        cout << (root->data);
        in_sned(root->rightchild);
    }
    return;
}
1
2
3
4
5
6
7
8
9
10

2.3. 后序遍历

void post_send(Node* root)
{
    if (root != NULL)
    {
        post_send(root->leftchild);
        post_send(root->rightchild);
        cout << (root->data);
    }
    return;
}
1
2
3
4
5
6
7
8
9
10

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

首先给出结构体：

struct Node
{
    int a;
    Node* Leftchild = nullptr;
    Node* Rightchild = nullptr;
}
1
2
3
4
5
6

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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
}
1
2
3
4
5
6
7
8
9

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

6. 二叉树镜面翻转

void Mirror_inversion(Node* p)
{
	if (p != NULL)
	{
		Mirror_inversion(p->Leftchild);
		Mirror_inversion(p->Rightchild);
		swap(p->Leftchild, p->Rightchild);
	}
}
1
2
3
4
5
6
7
8
9

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

9. 判断是否为子树

bool isSameTree(Node* t1, Node* t2) {
	// 考虑到后面子叶节点的左右节点，如果都为空就会返回True
	if (!t1 && !t2) {
		return true;
	}
	// 如果有一个节点有左右节点，而另一个节点没有的话就会返回false，而都有不会进入，都没有在上面会返回True
	if (!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;
	}
	// 每一个节点向下进行考虑，如果有一个是符合的就返回True
	return isSubtree(tree1->leftchild, tree2) || isSubtree(tree1->rightchild, tree2);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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 child
		root_1->rightchild = root_2->rightchild; // Handle right child
		return;
	}
	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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18