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

目录

一.树的遍历二.前序遍历三.中序遍历四.后序遍历五.层序遍历

一.树的遍历

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

二.前序遍历

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

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

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

//存储遍历结果的数组

vector v;

//前序遍历函数

vector 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 preorderTraversal(TreeNode* root)

{

vector v;//存储遍历结果的数组

stack 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）树的中序遍历指的是对树按照左、根、右的规律进行访问。

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

2）递归代码

//存储遍历结果的数组

vectorv;

//中序遍历函数

vector 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 inorderTraversal(TreeNode* root)

{

vectorv; //存储结果语句

stack 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）树的后序遍历指的是对树按照左、右、根的规律进行访问。

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

2）递归代码

//存储结果数组

vector v;

//后序遍历函数

vector 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 postorderTraversal(TreeNode* root) {

vectorres;

stacks;

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）层序遍历就是从上到下、从左到右输出节点

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

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

vector> levelOrder(TreeNode* root) {

vector> v;

if(root == NULL) return v; //特判

queue q; //队列

TreeNode* temp = NULL;

q.push(root);

while(!q.empty()) //队列为空跳出循环

{

vector ans; //存放每一层的数字

int n = q.size(); //每一层的个数

for (int i=0;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;

}