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

大家好，欢迎来到IT知识分享网。

一.树的遍历

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

二.前序遍历

遍历结果为：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; } 

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

三.中序遍历

遍历结果为：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; } 

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

四.后序遍历

遍历结果为：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; } 

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

五.层序遍历

遍历结果为： 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; }