preorder シーケンスと inorder シーケンスに基づいてツリーを再構築する (PHP 再帰実装)

class TreeNode{	public $data;	public $lchild = null;	public $rchild = null;	public function __construct($data='',$lchild=null,$rchild=null){		$this->data = $data;		$this->lchild = $lchild;		$this->rchild = $rchild;	}}

    //根据前序和中序，重建一颗树	//$pre 前序遍历的数组	//$mid 中序遍历的数组	function buildTree($pre,$mid){		$cnt = count($mid);		if($cnt<0) return null;		$root = $pre[0];		echo '$root==='.$root;		$node = new TreeNode($root);		$lenL = 0;		for($i=0;$i<$cnt;$i++){			if($mid[$i]== $root){				$lenL = $i;				break;			}		}		$lenR = $cnt -$lenL - 1;		if($lenL>0) $node->lchild = buildTree(array_slice($pre,1,$lenL),array_slice($mid,0,$lenL));		if($lenR>0) $node->rchild = buildTree(array_slice($pre,$lenL+1,$lenR),array_slice($mid,$lenL+1,$lenR));		return $node;	}		$mid = array(4,7,2,1,5,3,8,6);	$pre = array(1,2,4,7,3,5,6,8);	$node = buildTree($pre,$mid);	echo '<pre class="brush:php;toolbar:false">';	var_dump($node);	echo '

';

著作権表示: この記事はブロガーによるオリジナルの記事であり、ブロガーの許可なく複製することはできません。