Home >Backend Development >PHP Tutorial > 二叉树的中序遍历,该怎么解决

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

WBOY
WBOYOriginal
2016-06-13 12:57:291118browse

二叉树的中序遍历
假设二叉树的结构如下面的数组,数组下标0为根节点,1为左孩子节点,2为右孩子节点。前序遍历我已经实现,现在我希望能够中序遍历这个二叉树,希望大家给出好的方法。

<br />
//二叉树结构<br />
	$array=array("-",array("+",array("a"),array("*",array("b"),array("-",array("c"),array("d")))),array("/",array("e"),array("f")));<br />
	echo "<pre class="brush:php;toolbar:false">";<br />
	print_r($array);<br />
	echo "
";
//前序遍历代码
function bianli($array){
foreach($array as $value){
if(is_array($value)){
bianli($value);
}else{
echo $value;
}
}
}
echo bianli($array);

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


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

前序 -+a*b-cd/ef
中序 a+b*c-d-e/f
后序 abcd-*+ef/-
Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn