来者可追，往之不谏

努力提升自己

0%

二叉树与树的遍历

发表于 更新于 分类于
本文字数： 7.5k 阅读时长 ≈ 14 分钟

本文讲述树的遍历各种操作，层次遍历，前中后三种次序的遍历的迭代实现方式。其中包含力扣的相关题目。

开篇之前，先通过先序遍历的次序构建二叉树。(本片代码以二叉树为主，故多叉树结构暂不编写)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//二叉树结构体
struct BiTree {
	char val;
	BiTree* left=NULL;
	BiTree* right=NULL;
};
//先序创建二叉树
void createTree(BiTree* &root) {
	char ch;
	cin >> ch;
	if (ch != 'x') {//x表示为空结点
		root = new BiTree;
		root->val = ch;
		createTree(root->left);
		createTree(root->right);

	}
	else root = NULL;
}

树的层次遍历

​ 树的层次遍历与二叉树的层次遍历思路是一致的。先理解了二叉树的层次遍历的思路，再去理解树的层次遍历会轻松很多。层次遍历需要用到基本数据结构队列，在C++中的STL库中包含着队列的模板，如果不想再写个队列函数类在，直接用STL就可以了。

二叉树的层次遍历

​ 二层次遍历即按照树的层次从上向下一层一层的遍历。它的基本思路是先将根结点放入队列，然后取出队列中的元素，如果元素含有孩子，孩子再放进队列，如此反复，知道再也没有元素能够放进队列为止。当然这种思路实现不了按层次划分结点。若要分清那些结点在第一层，那些在第二层，思路有两种。

​ 第一种方法的思想是设立两个变量分别记录当前访问层的剩余元素个数和下一层中该访问的元素个数。代码与注释如代码块中所示

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
//二叉树的层次遍历
void hierarchicalTraversal1(BiTree* root) {
	cout << "层次遍历: "<<endl;
	queue<BiTree*>buff;
	int cur_level_size=0;//记录当前层元素个数
	int next_level_size=0;//记录下一层元素个数
	if (root) {
		//根节点存在，则入队列，当前层元素加一
		buff.push(root);
		cur_level_size++;
	}
	while (!buff.empty()) {
		//队首结点出队，当前层结点数-1，出队元素打印
		BiTree* node = buff.front();
		buff.pop();
		cout << node->val<<" ";
		cur_level_size--;//当前层元素出队操作完成，当前层结点数-1
		//左右孩子入队
		if (node->left) {
			buff.push(node->left);
			next_level_size++;
		}
		if (node->right) {
			buff.push(node->right);
			next_level_size++;
		}
		//一层访问完重置现场
		if (cur_level_size == 0) {
			cout << endl;
			cur_level_size = next_level_size;
			next_level_size = 0;
		}
	}
}

​ 第二种方法的思想非常巧妙，但整体思路是与法一一致。它在while循环里用for循环控制当前层的访问结点。思路依旧是先将根节点放进队列，再将节点的孩子放进队列，然后不断循环。不过每当一轮新的while循环时，此时的队列大小正好是当前层元素的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//二叉树的层次遍历
void hierarchicalTraversal2(BiTree* root) {
	cout << "层次遍历: "<<endl;
	queue<BiTree*>buff;
	int cur_level_size;//记录当前层元素个数
	if (root)buff.push(root);//root不为空入队
	//只要队列不为空即可继续遍历
	while (!buff.empty()) {
		cur_level_size = buff.size();
		//for循环将一层的元素入队并打印
		for (int i = 0;i < cur_level_size;i++) {
			BiTree* node = buff.front();//结点node接收队首元素
			buff.pop();
			cout << node->val << " ";
            //孩子结点入队
			if (node->left)buff.push(node->left);
			if (node->right)buff.push(node->right);
		}
		cout << endl;
	}
}

力扣题目

102. 二叉树的层序遍历 - 力扣（Leetcode）

N叉树的层次遍历

​ N叉树的层次遍历以力扣题429为例

​ 429. N 叉树的层序遍历 - 力扣（Leetcode）

题目描述

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

img

1
2
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

思路

二叉树层次遍历的两种都适用，此处代码以第二种方法展示

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<int>path;
        vector<vector<int>>res;
        using n=Node*;
        queue<n>que;
        if(root)que.push(root);
        while(!que.empty()){
            int cur_size=que.size();//千万不能在for循环中i<que.size(),因为for循环中que.size()动态变化
            for(int i=0;i<cur_size;i++){
                n node=que.front();
                que.pop();
                path.push_back(node->val);
                //队列先进先出，所以正序遍历children
                for(int j=0;j<node->children.size();j++){
                    if(node->children[j])que.push(node->children[j]);
                }
            }
            res.push_back(path);
            path.clear();
        }
        return res;

    }
};

层次遍历的刷题攻略

199. 二叉树的右视图 - 力扣（Leetcode）

637. 二叉树的层平均值 - 力扣（Leetcode）

515. 在每个树行中找最大值 - 力扣（Leetcode）

116. 填充每个节点的下一个右侧节点指针 - 力扣（Leetcode）

117. 填充每个节点的下一个右侧节点指针 II - 力扣（Leetcode）

树的先序遍历

先序遍历依旧先从二叉树讲起，在理解二叉树的基础上，多叉树的遍历无非就是换个方式访问孩子链表而已。

二叉树的先序遍历

与层次遍历不同，二叉树的先序遍历需要用到栈的数据结构。先序遍历的顺序是根—左—右，所以根节点先输出，之后向左遍历，其次再访问右结点。这里有个细节需要注意，由于栈的特性是后进先出，在孩子结点入栈的时候，需要先将右孩子入栈，左孩子后入栈，这是因为之后要先访问左孩子导致的。当然，N叉树的遍历过程也需要注意这个细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//先序遍历迭代实现
void PreOrderTraversal(BiTree* root) {
	cout << "先序遍历: ";
	stack<BiTree*>st;
	if (root)st.push(root);
	while (!st.empty()) {
		BiTree* node = st.top();//取栈顶元素
		st.pop();//栈顶元素出栈
		cout << node->val << " ";
		//将左右孩子结点加入到栈中
		if (node->right)st.push(node->right);//此处需谨慎，先右边进去左边再进去，因为下一个要先访问左边的
		if (node->left)st.push(node->left);
	}
	cout << endl;

}

N叉树的先序遍历

589. N 叉树的前序遍历 - 力扣（Leetcode）

题目描述

给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

img

1
2
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]

思路

整体思路与二叉树前序遍历思路一致。但在处理孩子结点时要改一改代码。而且孩子之间的顺序是从左到右访问的，所以孩子结点要从后向前入栈，即逆序入栈。

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    using N=Node*;
    vector<int>res;
    void recursion(N root){
        if(!root)
        return ;
        else{
            res.push_back(root->val);
            for(int i=0;i<root->children.size();i++){
                recursion(root->children[i]);
            }
        }
    }
    vector<int> preorder(Node* root) {
        
       recursion(root);
        return res;
    }
};

二叉树的中序遍历

二叉树的中序遍历思路与先序遍历思路差别很大，不要想着照着先序遍历的代码改改就能实现。中序遍历的顺序是左—根—右，路过的结点都要存到栈中，直到遍历到了空结点，此时才可以取出栈顶元素，打印输出。之后就要开始走右孩子的道路了，不然的话会原地打转。

另外，while循环的判定条件不能像先序遍历那样，只判定栈空不空就行了。这样会导致根节点的右半子树无法访问，因为根节点出栈的时候，根节点的右孩子还没有入栈，然而根节点必定是栈底元素，根节点一出去，栈为空，while判定条件不成立，右孩子未访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//中序遍历迭代实现
void  InOrderTraversal(BiTree* root) {
	cout << "中序遍历: ";
	stack<BiTree*>st;
	BiTree* cur = root;
	while (cur!=NULL||!st.empty()) {//一定要加cur!=NULL，否则根节点出去后栈已经变空了，根节点的右边无法访问
		//遍历到非空结点一直向左遍历，找到最左边的结点
		if (cur != NULL) {
			st.push(cur);
			cur = cur->left;
		}
		//遍历到空结点，返回栈中的上一个结点，然后向右遍历
		else {
			cur = st.top();
			st.pop();
			cout << cur->val<<" ";
			cur = cur->right;
		}
	}
	cout << endl;
}

树的后序遍历

二叉树的后序遍历

用迭代的思想实现二叉树的后序遍历有一个简单的方法，后序遍历是左—右—根,如果把它逆置过来，不就变成了根—右—左。这不就是将先序遍历改改代码嘛。把上文讲述的先序遍历的细节理解了，用这种方式写后序遍历不成问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//后序遍历的两种实现
//左右根->根右左的逆序
void PostOrderTraversal1(BiTree* root) {
	cout << "后序遍历：";
	stack<BiTree*>st;
	vector<char>res;
	if (root)st.push(root);
	while (!st.empty()) {
		BiTree* node = st.top();
		st.pop();
		res.push_back(node->val);//将遍历结果存到容器中
		if (node->left)st.push(node->left);
		if (node->right)st.push(node->right);
	}
	reverse(res.begin(), res.end());//将保存结果的容器逆置即为所求
	for (auto& c : res)
		cout << c<<" ";
}

N叉树的后序遍历

590. N 叉树的后序遍历 - 力扣（Leetcode）

题目描述

给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

img

1
2
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]

思路

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        using n=Node*;
        vector<int>res;
        stack<n>st;
        if(root)st.push(root);
        while(st.size()){
            n node=st.top();
            st.pop();
            res.push_back(node->val);
            for(int i=0;i<node->children.size();i++){
                if(node->children[i])
                    st.push(node->children[i]);
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

代码测试结果

将上述讲述的代码做一个测试

1
2
3
4
5
6
7
8
BiTree* root = new BiTree;
	cout << "先序构建二叉树，x表示空结点，输入一个元素: "<<endl;
	createTree(root);//1 2 4 6 x x 7 x x 5 x x 3 x 3 x x
	hierarchicalTraversal1(root);//层次遍历
	hierarchicalTraversal2(root);//层次遍历
	PreOrderTraversal(root);//先序遍历
	InOrderTraversal(root);//中序遍历
	PostOrderTraversal1(root);//后序遍历

运行结果

先序构建二叉树，x表示空结点，输入一个元素:
1 2 4 6 x x 7 x x 5 x x 3 x 3 x x
层次遍历:
1
2 3
4 5 3
6 7
层次遍历:
1
2 3
4 5 3
6 7
先序遍历: 1 2 4 6 7 5 3 3
中序遍历: 6 4 7 2 5 1 3 3
后序遍历：6 7 4 5 2 3 3 1