首页 > 代码库 > 一步一步写算法(之二叉树深度遍历)

一步一步写算法(之二叉树深度遍历)

原文: 一步一步写算法(之二叉树深度遍历)

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱: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


建议:

    上面的算法虽然比较简单,也比较基础,但是还是建议朋友们应该多加练习和锻炼。    


一步一步写算法(之二叉树深度遍历)