当前位置:Gxlcms > PHP教程 > 二叉树的中序遍历,该怎么解决

二叉树的中序遍历,该怎么解决

时间:2021-07-01 10:21:17 帮助过:27人阅读

二叉树的中序遍历
假设二叉树的结构如下面的数组,数组下标0为根节点,1为左孩子节点,2为右孩子节点。前序遍历我已经实现,现在我希望能够中序遍历这个二叉树,希望大家给出好的方法。
  1. <br>
  2. //二叉树结构<br>
  3. $array=array("-",array("+",array("a"),array("*",array("b"),array("-",array("c"),array("d")))),array("/",array("e"),array("f")));<br>
  4. echo "<pre class="brush:php;toolbar:false layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>";<br></li><li>print_r($array);<br></li><li>echo "</li></ol></pre>";<br>
  5. //前序遍历代码<br>
  6. function bianli($array){
  7. <br>
  8. foreach($array as $value){<br>
  9. if(is_array($value)){<br>
  10. bianli($value);<br>
  11. }else{<br>
  12. echo $value;<br>
  13. }<br>
  14. }<br>
  15. }<br>
  16. echo bianli($array);<br>

PS(另求一个能下载英文学术论文的网站,毕设英文翻译需要用到,我从谷歌学术上面找的PDF版很不清晰,不知道有没有其他网站可以下载,希望大家能够推荐)


------解决方案--------------------
你给出的二叉树表示的不严密,每个节点宜用关联数组而不是下标数组表示
好在你的树是满的,不然极易产生误解
你的每个节点的下标分别表示
0 根 1 左孩子 2 右孩子
由二叉树遍历的定义,有
  1. /* 前序遍历 */<br>
  2. function DLR($F) {<br>
  3. if(isset($F[0])) echo $F[0];<br>
  4. if(isset($F[1])) DLR($F[1]);<br>
  5. if(isset($F[2])) DLR($F[2]);<br>
  6. }<br>
  7. /* 中序遍历 */<br>
  8. function LDR($F) {<br>
  9. if(isset($F[1])) LDR($F[1]);<br>
  10. if(isset($F[0])) echo $F[0];<br>
  11. if(isset($F[2])) LDR($F[2]);<br>
  12. }<br>
  13. /* 后序遍历 */<br>
  14. function LRD($F) {<br>
  15. if(isset($F[1])) LRD($F[1]);<br>
  16. if(isset($F[2])) LRD($F[2]);<br>
  17. if(isset($F[0])) echo $F[0];<br>
  18. }<br>

前序 -+a*b-cd/ef
中序 a+b*c-d-e/f
后序 abcd-*+ef/-

人气教程排行