［算法］二叉树的遍历：前序，中序与后序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了［算法］二叉树的遍历：前序，中序与后序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7399字，纯文字阅读大概需要11分钟。

内容图文

二叉树的遍历是二叉树的众多算法的基础。主要有，前序，中序与后序。

对于以下二叉树：

前序：12354

中序：21543

后序：24531

笔者实现了三种遍历方式:

1 前序：递归版本比较简单，只需要改变push_back操作的位置即可。

vector<int> PreOrderTraverse2(TreeNode *root)
{
	vector<int> nodes;
	vector<int> temp;
	if(root == NULL) return nodes;
	nodes.push_back(root->val);
	temp = PreOrderTraverse2(root->left);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	temp = PreOrderTraverse2(root->right);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	return nodes;

}

前序迭代版本，步骤如下：

（1）首先访问根节点root，先将root节点输出，压入堆栈，

（2）再考虑root节点的左子树，左子树也是一颗二叉树，重复（1）。

（3）某一步的左子树为空，那么该节点左子树已访问完毕，弹出栈顶，访问该节点的右子树，重复（1）即可。

很简单，只需要记住，在将节点压入堆栈时，该节点就已被访问，再访问完左孩子之后，再考虑右孩子所在的二叉树。

vector<int> PreOrderTraverse(TreeNode *root)
{
	vector<int> nodes;
	stack<TreeNode *> s;
	if(root == NULL) return nodes;
	TreeNode *temp = root;
	while(temp || !s.empty())
	{
		while(temp)
		{
			s.push(temp);//入栈之前就访问
			nodes.push_back(temp->val);
			temp = temp->left;
		}//左子树访问完毕
		temp = s.top();
		s.pop();
		temp = temp->right;
	}
	return nodes;
}

2 中序，递归版本：

vector<int> InOrderTraverse2(TreeNode *root)
{
	vector<int> nodes;
	vector<int> temp;
	if(root == NULL) return nodes;
	temp = InOrderTraverse2(root->left);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	nodes.push_back(root->val);
	temp = InOrderTraverse2(root->right);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	return nodes;

}

迭代版本：

（1）首先访问根节点root，压入堆栈。

（2）访问root的左子树，重复（1）即可。

（3）如果某节点左子树为空，那么该节点输出，并考察其右子树，重复（1）即可。

PS：节点入栈使不访问，遇到节点就入栈，直到栈顶左子树访问完毕，那么将栈顶弹出，考虑右子树，重复即可。

vector<int> InOrderTraverse(TreeNode *root)
{
	vector<int> nodes;
	if(root == NULL) return nodes;
	TreeNode *temp = root;
	stack<TreeNode *> s;

	while(temp || !s.empty())
	{
		while(temp)
		{
			s.push(temp);
			temp = temp->left;
		}// 左子树完毕
		temp = s.top();
		nodes.push_back(temp->val);
		s.pop();
		temp = temp->right;
	}
	return nodes;
}

3 后序，递归版本：

vector<int> PostOrderTraverse2(TreeNode *root)
{
	vector<int> nodes;
	vector<int> temp;
	if(root == NULL) return nodes;
	temp = PostOrderTraverse2(root->left);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	temp = PostOrderTraverse2(root->right);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	nodes.push_back(root->val);
	return nodes;

}

迭代版本：步骤如下：

PS：遇到根节点root，分两种情况讨论，如果根节点的右子树还没被访问，那么根节点入栈；否则输出根节点。

vector<int> PostOrderTraverse(TreeNode *root)
{
	vector<int> nodes;
	if(root == NULL) return nodes;
	TreeNode *temp = root;
	TreeNode *pre = root; //记录前一次访问的节点
	stack<TreeNode *> s;
	while(temp || !s.empty())
	{
		while(temp)
		{
			s.push(temp);
			temp = temp->left;
		}
		temp = s.top();
		if (temp->right == NULL || pre == temp->right)
		{
			nodes.push_back(temp->val);
			pre = temp;
			s.pop();
			temp = NULL;//保证不重复访问
		}
		else
		{
			temp = temp->right;
		}
	}
	return nodes;
}

后序遍历的递归版本比较复杂。自己在编写代码时会出现死循环，因为出现了重复访问，因此上述的temp=NULL语句很重要。

后记：上述3种算法的空间复杂度均为O（n）。

完整的代码为：

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

struct TreeNode{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x):val(x),left(NULL),right(NULL){}
};

vector<int> InOrderTraverse2(TreeNode *root)
{
	vector<int> nodes;
	vector<int> temp;
	if(root == NULL) return nodes;
	temp = InOrderTraverse2(root->left);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	nodes.push_back(root->val);
	temp = InOrderTraverse2(root->right);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	return nodes;

}

vector<int> PreOrderTraverse2(TreeNode *root)
{
	vector<int> nodes;
	vector<int> temp;
	if(root == NULL) return nodes;
	nodes.push_back(root->val);
	temp = PreOrderTraverse2(root->left);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	temp = PreOrderTraverse2(root->right);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	return nodes;

}


vector<int> PostOrderTraverse2(TreeNode *root)
{
	vector<int> nodes;
	vector<int> temp;
	if(root == NULL) return nodes;
	temp = PostOrderTraverse2(root->left);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	temp = PostOrderTraverse2(root->right);
	for(vector<int>::size_type i = 0 ; i != temp.size() ; ++i)
		nodes.push_back(temp[i]);
	nodes.push_back(root->val);
	return nodes;

}

vector<int> PreOrderTraverse(TreeNode *root)
{
	vector<int> nodes;
	stack<TreeNode *> s;
	if(root == NULL) return nodes;
	TreeNode *temp = root;
	while(temp || !s.empty())
	{
		while(temp)
		{
			s.push(temp);//入栈之前就访问
			nodes.push_back(temp->val);
			temp = temp->left;
		}
		temp = s.top();
		s.pop();
		temp = temp->right;
	}
	return nodes;
}

vector<int> InOrderTraverse(TreeNode *root)
{
	vector<int> nodes;
	if(root == NULL) return nodes;
	TreeNode *temp = root;
	stack<TreeNode *> s;

	while(temp || !s.empty())
	{
		while(temp)
		{
			s.push(temp);
			temp = temp->left;
		}
		temp = s.top();
		nodes.push_back(temp->val);
		s.pop();
		temp = temp->right;
	}
	return nodes;
}

vector<int> PostOrderTraverse(TreeNode *root)
{
	vector<int> nodes;
	if(root == NULL) return nodes;
	TreeNode *temp = root;
	TreeNode *pre = root; //记录前一次访问的节点
	stack<TreeNode *> s;
	while(temp || !s.empty())
	{
		while(temp)
		{
			s.push(temp);
			temp = temp->left;
		}
		temp = s.top();
		if (temp->right == NULL || pre == temp->right)
		{
			nodes.push_back(temp->val);
			pre = temp;
			s.pop();
			temp = NULL;//保证不重复访问
		}
		else
		{
			temp = temp->right;
		}
	}
	return nodes;
}



int main()
{
	vector<int> nodes;
	TreeNode *root = new TreeNode(1);
	TreeNode *node2 = new TreeNode(2);
	TreeNode *node3 = new TreeNode(3);
	TreeNode *node4 = new TreeNode(4);
	TreeNode *node5 = new TreeNode(5);
	root->left = node2;
	root->right = node3;
	node5->right = node4;
	node3->left = node5;
	
	cout << "InOrder recursively..." << endl;
	nodes = InOrderTraverse2(root);
	for(vector<int>::size_type i = 0; i != nodes.size(); i++)
		cout << nodes[i] << " ";
	cout << endl;
	cout << "InOrder iterativelly..." << endl;
	nodes = InOrderTraverse(root);
	for(vector<int>::size_type i = 0; i != nodes.size(); i++)
		cout << nodes[i] << " ";
	cout << endl;
	cout << "PreOrder recursively..." << endl;
	nodes = PreOrderTraverse2(root);
	for(vector<int>::size_type i = 0; i != nodes.size(); i++)
		cout << nodes[i] << " ";
	cout << endl;
	cout << "PreOrder iterativelly..." << endl;
	nodes = PreOrderTraverse(root);
	for(vector<int>::size_type i = 0; i != nodes.size(); i++)
		cout << nodes[i] << " ";
	cout << endl;
	cout << "PostOrder recursively..." << endl;
	nodes = PostOrderTraverse2(root);
	for(vector<int>::size_type i = 0; i != nodes.size(); i++)
		cout << nodes[i] << " ";
	cout << endl;
	cout << "PostOrder iterativelly..." << endl;
	nodes = PostOrderTraverse(root);
	for(vector<int>::size_type i = 0; i != nodes.size(); i++)
		cout << nodes[i] << " ";
	cout << endl;
}

原文：http://blog.csdn.net/xuqingict/article/details/19089727

内容总结

以上是互联网集市为您收集整理的［算法］二叉树的遍历：前序，中序与后序全部内容，希望文章能够帮你解决［算法］二叉树的遍历：前序，中序与后序所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1289973.html

来源：【匿名】

【上一篇】由二叉树的层序和中序建树【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【［算法］二叉树的遍历：前序，中序与后序】教程文章相关的互联网学习教程文章

二叉树的遍历是二叉树的众多算法的基础。主要有，前序，中序与后序。对于以下二叉树：前序：12354中序：21543后序：24531笔者实现了三种遍历方式:1 前序：递归版本比较简单，只需要改变push_back操作的位置即可。vector<int> PreOrderTraverse2(TreeNode *root) {vector<int> nodes;vector<int> temp;if(root == NULL) return nodes;nodes.push_back(root->val);temp = PreOrderTraverse2(root->left);for(vector<int>::size_type...

二叉树的非递归遍历（借鉴递归思想实现非递归遍历）【代码】

1// 树结点定义2 typedef struct TNode 3{ 4int value; 5 TNode *left; 6 TNode *right; 7 }*PTNode;1. 前序遍历的非递归实现（借鉴递归思想实现）思想：访问到一结点时，先将其入栈，假设入栈节点为P。访问P，将P的右孩子和左孩子依次入栈，这样就保证了每次左孩子在右孩子前面被访问。 1void preOrderNoneRecursion(PTNode root)2{3if(root == NULL)4return;5 PTNode p = root;6 stack<PTNode> nodeStack;7 n...

输入某二叉树的前序遍历和中序遍历的结果，重建出该二叉树【代码】【图】

//================================================================== // 《剑指Offer——名企面试官精讲典型编程题》代码 // 作者：何海涛 //==================================================================// 面试题7：重建二叉树 // 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输 // 入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, // 2, 4, 7, 3, 5, 6, 8}和中...

【二叉树】二叉树的创建与遍历【代码】

一、定义二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。二、性质在非空二叉树中，第i层的结点总数不超过, i>=1；深度为h的二叉树最多有个结点(h>=1)，最少有h个结点；对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；具有n个结点的完全二叉树的深度为（注：[ ]表示向下取整）有N个...

【二叉树】二叉树的创建与遍历【代码】

二叉树算法的收集【代码】

java学习-排序二叉树【代码】【图】

（排序）二叉树的创建及中序遍历写起来比C复杂一点，思路大同小异~ 1package Collection;2 3import java.util.ArrayList;4import java.util.List;5/* 6 * （排序）二叉树的创建及中序遍历7*/ 8publicclass Node {9public Node LNode; 10public Node RNode; 11public Object value; // 结点的值1213publicvoid add(Object v) { // 传入的参数是要加入二叉树的新结点的值，是数值！！！14if (this.value == null) { 15 v...

二叉树的迭代器【代码】

仅有遍历算法是不够的，在许多应用中，我们还需要对遍历本身进行抽象。假如有一个求和的函数sum，我们希望它能应用于链表，数组，二叉树等等不同的数据结构。这时，我们可以抽象出迭代器(Iterator)的概念，通过迭代器把算法和数据结构解耦了，使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义成:int sum(Iterator from, Iterator to)链表作为一种线性结构，它的迭代器实现非常简单和直观，而二叉树的迭代器实现则不...

二叉树前序遍历C#实现【代码】

迭代实现： 11/**2 2 * Definition for a binary tree node.3 3 * public class TreeNode {4 4 * public int val;5 5 * public TreeNode left;6 6 * public TreeNode right;7 7 * public TreeNode(int x) { val = x; }8 8 * }9 9 */1010publicclass Solution { 1111public IList<int> PreorderTraversal(TreeNode root) { 1212 List<int> result=new List<int>(); 1313if (root==null) 1414return...

lintcode 容易题：Binary Tree Preorder Traversal 二叉树的前序遍历【代码】【图】

题目：二叉树的前序遍历给出一棵二叉树，返回其节点值的前序遍历。样例给出一棵二叉树 {1,#,2,3},12/3 返回 [1,2,3].挑战你能使用非递归实现么？解题：通过递归实现，根节点->左节点->右节点Java程序：/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* ...

二叉树总结(一)概念和性质【代码】【图】

一、树的概念树是一些点的集合，这个集合可以为空，若不为空，则它是由一个根节点和0个或多个为空的子树组成，且每个子树都被一条来自根节点的有向边相连。树叶：没有儿子的节点；兄弟：具有相同父亲的节点；类似还有祖父和孙子节点。路径：节点n1，n2，n3，...，nk的一个序列，使得对于1 <= i <= k节点ni是ni+1的父亲；路径的长为路径上边的数量，即K+1。深度：某节点的深度为树根到该节点的唯一路径的长度。层次：深度相同的节点...

二叉树相关

int width(BTree *bt){ BTree *p=bt; if(bt)return 0; BTree *q[100]; int front=0,rear=0;//队头指针，队尾指针 int last=0;//同一层最右结点在队列中位置 int temp=0,maxw=0;//当前层宽度与最大宽度 q[rear]=bt; while(front<=last) { p=q[front++];temp++;//同层元素加1; if(p->lchild)q[rear++]=p->lchild; if(p->rchild)q[rear++]=p->rchild; if(front>last)//一层结...

二叉树的基础题目学习（EPI）【图】

1.判断是个二叉树是不是平衡二叉树。二叉树的定义都是利用递归的方法，所以二叉树有着天然的递归属性。所以一般情况下，递归解决二叉树问题中，递归解法比较简洁。平衡二叉树的定义是左子树和右子树均是平衡二叉树，并且左子树和右子树的高度差不超过1，三个条件缺一不可。根据递归的定义，递归实现起来需要返回子树的高度，又要返回子树是否平衡的属性，所以判断平衡二叉树的递归算法需要传会两个参数，所以把递归函数原型...

LeetCode剑指offer二叉树系列【代码】

LeetCode剑指offer二叉树系列07 重建二叉树题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：3/ 9 20/ 15 7来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof 著作权归领扣网络所有。商业转载请联系官...

数据结构（二十一）二叉树遍历算法的应用与二叉树的建立

一、顺序存储结构对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。　　二、二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。　　三、完全二叉树可以将相应下标的结点存到数组的相应下标的位置上，对于一般的二叉树来说，完全可以将其...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...