【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
深度遍历是软件开发中经常遇到的遍历方法。常用的遍历方法主要有下面三种:(1)前序遍历;(2)中序遍历;(3)后序遍历。按照递归的方法,这三种遍历的方法其实都不困难,前序遍历就是根-左-右,中序遍历就是左-根-右,后续遍历就是左-右-根。代码实现起来也不复杂。
1)前序遍历
void preorder_traverse(TREE_NODE* pTreeNode)
{
if(pTreeNode){
printf("%d", pTreeNode->data);
preorder_traverse(pTreeNode->left);
preorder_traverse(pTreeNode->right);
}
}
2)中序遍历
void inorder_traverse(TREE_NODE* pTreeNode)
{
if(pTreeNode){
inorder_traverse(pTreeNode->left);
printf("%d", pTreeNode->data);
inorder_traverse(pTreeNode->right);
}
}
3)后序遍历
void afterorder_traverse(TREE_NODE* pTreeNode)
{
if(pTreeNode){
afterorder_traverse(pTreeNode->left);
afterorder_traverse(pTreeNode->right);
printf("%d", pTreeNode->data);
}
}
4)后序遍历的一个应用
上面的遍历方法看上去都比较简单,那他们的应用是什么呢?我们可以拿编程语言中语法树举一个例子。比如说,现在我们需要计算这样一个简单的表达式:
int m = 1 + 2 * 5 -4 / 2;
那么这个表达式的语法树可能是这样的,其中末尾的分号已经删除。
现在,我们对上面的表达式进行后序遍历,结果应该是这样的: m、1、2、5、*、4、2、\、-、+、=。那么这个输出的表达式,我们应该怎么计算呢?其实不复杂,我们只要发现连续两个数字和一个相连的符号就可以计算了,上面的表达式计算顺序应该是这样的:
/*
* =
* / \
* m -
* / \
* + /
* / \ / \
* 1 * 4 2
* / \
* 2 5
*/
a)m、1、2、5、*、+、4、2、/、-、=
b)m、1、10、+、4、2、/、-、=
c)m、11、4、2、/、-、=
d)m、11、2、-、=
e)m、9、=
f)m
建议:
上面的算法虽然比较简单,也比较基础,但是还是建议朋友们应该多加练习和锻炼。
分享到:
相关推荐
二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法
二叉树遍历算法,包括创建二叉树,先序,中序以及后序遍历等。
算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法...
二叉树的建立和遍历算法 数据结构课程设计用
包括了二叉树的各种递归与非递归的遍历算法 还可对二叉树所有结点求和
层次遍历二叉树
实现二叉树的深度遍历广度遍历等关于二叉树的基本操作
遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历...
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
二叉树遍历算法应用各种算法包括遍历创建求深度等
按层次遍历二叉树的算法 简单易懂 按层次遍历二叉树的算法 简单易懂
实验八:二叉树的遍历算法 以下是二叉树建立的两种方法,三种遍历和计算结点数的综合程序.(读者有建议可提出)
C语言二叉树遍历前序非递归算法,简单易懂,正确无误
建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
小小学习,C语言数据结构,中序遍历二叉树非递归算法
数据结构课程设计--二叉树遍历及其应用、对树的先序遍历、后序遍历、中序遍历、层序遍历、二叉树的深度及其叶子树、并打印树形。
经典的数据结构问题:二叉树非递归遍历算法实现 二叉树递归遍历算法实现