• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++算法之二叉树深度遍历

OC/C/C++ 水墨上仙 1564次浏览

深度遍历是软件开发中经常遇到的遍历方法。常用的遍历方法主要有下面三种:(1)前序遍历;(2)中序遍历;(3)后序遍历。按照递归的方法,这三种遍历的方法其实都不困难,前序遍历就是根-左-右,中序遍历就是左-根-右,后续遍历就是左-右-根。代码实现起来也不复杂。
转自:http://blog.csdn.net/feixiaoxing/article/details/6897644

&nbsp&nbsp&nbsp&nbsp1)前序遍历

void preorder_traverse(TREE_NODE* pTreeNode)  
{  
    if(pTreeNode){  
        printf("%d", pTreeNode->data);  
        preorder_traverse(pTreeNode->left);  
        preorder_traverse(pTreeNode->right);  
    }  
}  
 

&nbsp&nbsp&nbsp2)中序遍历

void inorder_traverse(TREE_NODE* pTreeNode)  
{  
    if(pTreeNode){  
        inorder_traverse(pTreeNode->left);  
        printf("%d", pTreeNode->data);  
        inorder_traverse(pTreeNode->right);  
    }  
}  
  

&nbsp&nbsp3)后序遍历

void afterorder_traverse(TREE_NODE* pTreeNode)  
{  
    if(pTreeNode){  
        afterorder_traverse(pTreeNode->left);  
        afterorder_traverse(pTreeNode->right);  
        printf("%d", pTreeNode->data);  
    }  
}  

&nbsp&nbsp&nbsp&nbsp4)后序遍历的一个应用
&nbsp&nbsp&nbsp&nbsp上面的遍历方法看上去都比较简单,那他们的应用是什么呢?我们可以拿编程语言中语法树举一个例子。比如说,现在我们需要计算这样一个简单的表达式:
&nbsp&nbsp&nbsp&nbsp&nbspint&nbspm&nbsp=&nbsp&nbsp1&nbsp+&nbsp&nbsp2&nbsp&nbsp*&nbsp5&nbsp&nbsp-4&nbsp/
&nbsp&nbsp&nbsp&nbsp&nbsp那么这个表达式的语法树可能是这样的,其中末尾的分号已经删除。
&nbsp&nbsp&nbsp&nbsp现在,我们对上面的表达式进行后序遍历,结果应该是这样的:&nbspm、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

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


喜欢 (0)
加载中……