树的遍历（四种全）｜C++

一.树的遍历

树的遍历也叫树的搜索，是指按照某种规则对树的节点进行一遍不重复的访问。按照不同的方式可以分为树的前序遍历、中序遍历、后序遍历和层序遍历。

二.前序遍历

1）树的前序遍历指的是对树按照根、左、右的规律进行访问。

遍历结果为：F, B, A, D, C, E, G, I, H

2）递归代码实现（对于前序、中序、后序遍历的递归实现非常的相似，只是改变输出数组语句的位置）

	//存储遍历结果的数组
	vector<int> v;
	//前序遍历函数
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==nullptr) return v;
        v.emplace_back(root->val); //输入数组语句
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return v;
    }
1
2
3
4
5
6
7
8
9
10

3）迭代代码（使用了一个栈，速度比递归更快）

思路：

$\bullet$ 先将根的左孩子依次入栈，入栈的同时进行访问，直到为空

$\bullet$ 栈顶元素出栈，如果其右孩子为空，继续执行2

$\bullet$ 若右孩子不空，则执行1

vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> v;//存储遍历结果的数组
        stack<TreeNode*> s; //栈，模拟搜索
        TreeNode* temp = root;
        //循环条件，只有当遍历完所有节点并且栈为空的时候才终止
        while(temp || !s.empty())
        {
        	//当指向不为空节点时
            if(temp != nullptr)
            {
                v.emplace_back(temp->val);
                s.push(temp);  //将该结点入栈
                temp = temp->left; //根据前序遍历的要求，指向它的左子节点
            }else
            {
            	//当左边已经完全搜完时，弹出栈顶节点并找到它的右子节点继续进行搜索
                temp = s.top()->right;
                s.pop();
            }
        }
        return v;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三.中序遍历

1）树的中序遍历指的是对树按照左、根、右的规律进行访问。

遍历结果为：A, B, C, D, E, F, G, H, I

2）递归代码

	//存储遍历结果的数组
	vector<int>v;
    //中序遍历函数
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==nullptr) return v;
        inorderTraversal(root->left);
        v.emplace_back(root->val);  //输入数组语句
        inorderTraversal(root->right);
        return v;
    }
1
2
3
4
5
6
7
8
9
10

3）迭代代码

思路：

$\bullet$ 先将根的左孩子依次入栈，直到为空

$\bullet$ 栈顶元素出栈并访问，如果其右孩子为空，继续执行2

$\bullet$ 若右孩子不空，则执行1

vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int>v; //存储结果语句
        stack<TreeNode*> s;
        TreeNode* temp = root;

        while(1)
        {
        	//先找到最左边的节点，并将经过的节点入队
            while(temp)
            {
                s.push(temp);
                temp = temp->left;
            }           
            //当栈为空时则退出循环
            if(s.empty()) break;
            //加入栈顶节点的值，即最左边的节点的值
            v.emplace_back(s.top()->val);
            //查找该节点的右子节点
            temp = s.top()->right;
            s.pop();
        }
        return v;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四.后序遍历

1）树的后序遍历指的是对树按照左、右、根的规律进行访问。

遍历结果为：A, C, E, D, B, H, I, G, F.

2）递归代码

	//存储结果数组
 	vector<int> v;
 	//后序遍历函数
    vector<int> postorderTraversal(TreeNode* root) {
        if(root == nullptr) return v;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        v.emplace_back(root->val); //输入语句
        return v;
    }
1
2
3
4
5
6
7
8
9
10

3）迭代代码（补充）

思路：

$\bullet$ 先将根的左孩子依次入栈，直到为空

$\bullet$ 读栈顶元素，若其右孩子不空且未被访问过，则将右子树执行1

$\bullet$ 若其右子树为空或者已被访问过，栈顶元素出栈并访问

注意：由于在第二步中不知道当前返回是左子树的返回还是右子树的返回，所以设置了一个辅助指针r，指向最近访问过的结点

vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>s;
        TreeNode* temp=root;
        TreeNode* r=nullptr;
        while(temp || !s.empty())
        {
            if(temp)
            {
                s.push(temp);
                temp=temp->left;
            }else
            {
                temp=s.top();
                if(temp->right && temp->right!=r)
                    temp=temp->right;
                else
                {
                    res.emplace_back(temp->val);
                    s.pop();
                    r=temp;
                    temp=nullptr;
                }
            }
        }
        return res;
    }
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

五.层序遍历

1）层序遍历就是从上到下、从左到右输出节点

遍历结果为： F, B, G, A, D, I, C, E, H.

2）迭代代码（我们把每一层放在一个数组中，最后将它们再放入一个总的数组中）

   vector<vector<int>> levelOrder(TreeNode* root) {
     vector<vector<int>> v;
     if(root == NULL) return v;  //特判
     queue<TreeNode*> q;  //队列
     TreeNode* temp = NULL;
     q.push(root);
     while(!q.empty()) //队列为空跳出循环
     {
         vector<int> ans; //存放每一层的数字
         int n = q.size(); //每一层的个数
         for (int i=0;i<n;i++)
         {
             temp = q.front();
             q.pop();
             ans.emplace_back(temp->val);
             if(temp->left != NULL) q.push(temp->left);
             if(temp->right != NULL) q.push(temp->right);
         }
         v.emplace_back(ans);
     }
     return v;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22