石家庄模板建站系统,建筑工程造价网,一键seo提交收录,企业网站的网址有哪些非递归实现二叉树的前序/后序/中序遍历 中序遍历 // arr[1]// arr[2] arr[3] // arr[4] arr[5] arr[6] // arr[7] arr[8]如上数据, 以栈来代替递归实现,输出为4,2,(遍历右元素7,5,8).那么就要想办法以上面的方法入栈4,2… 非递归实现二叉树的前序/后序/中序遍历 中序遍历 // arr[1]// arr[2] arr[3] // arr[4] arr[5] arr[6] // arr[7] arr[8]如上数据, 以栈来代替递归实现,输出为4,2,(遍历右元素7,5,8).那么就要想办法以上面的方法入栈4,2,7,5,8的反序8,5,7,2,4 左节点出栈后的下个节点肯定是其父节点,右节点(在没有子节点的情况下)出栈后下个节点肯定是根左节点(如节点4的下个节点是节点2, 节点8的下个节点是节点1) step 1 遍历左节点,入栈 step 2 出栈,然后遍历该节点的右节点回到step1 以下为demo: // arr[1]// arr[2] // arr[4] arr[5] // arr[7] arr[8]push:1,2,4 pop:4 push:7 pop:7 pop:2 push:5 pop:5 push:8 pop:8 pop:1 总结: 遍历全部左节点 pop一个节点,push右节点 回到step1 先序遍历 与中序遍历类似,把输出的地方改为Push的位置就可以了,因为先序总是以根节点开始,然后再访问左右节点 后序遍历 push:1,2,4 pop:4 {prev:2,cur4} push:5 {prev:4,cur2} push:7 {prev:2,cur5} pop:7 {prev:5,cur7} push:8 {prev:7,cur5} pop:8 {prev:5,cur8} pop:5 {prev:8,cur5} pop:2 {prev:5,cur2} … 后序遍历比较麻烦一些. 按照以下规则来记忆: 当节点为叶节点时出栈 左节点出栈后,继续出栈右节点,再出栈自身节点,如果没有右节点则出栈自身节点 使用双栈实现:应该说是最简单的 pop一个节点到一个栈,然后push左右节点到另一个栈 不贴代码,代码下面有 参考此贴:http://www.cnblogs.com/MichaelYin/archive/2010/12/23/1915316.html http://www.cnblogs.com/Jax/archive/2009/12/28/1633691.html 关于递归算法和非递归算法的区别和转换的文章 http://wenku.baidu.com/view/0c2409c55fbfc77da269b1c8.html
