php如何实现根据前序和中序遍历结果重建二叉树（代码）

内容导读

收集整理的这篇技术教程文章主要介绍了php如何实现根据前序和中序遍历结果重建二叉树（代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2481字，纯文字阅读大概需要4分钟。

内容图文

本篇文章给大家带来的内容是关于php如何实现根据前序和中序遍历结果重建二叉树（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
1.前序遍历是中，左，右；中序遍历是左，中，右
2.前序遍历的第一个是根结点，中序遍历数组中从开始到根结点的所有是左子树，可以知道左子树的个数，根结点右边的是右子树
3.前序遍历除去0位置的，从1到左子树个数位置是左子树，其他的是右子树
4.确定四个数组，前序左子树数组，前序右子树数组，中序左子树数组，中序右子树数组；递归调用

reConstructBinaryTree(pre,in)    if(pre.length) return null//递归终止条件    root=pre[0]    Node=new Node(root)    //在中序中找根结点的位置    p=0    for p;p<pre.length;p++        if in[p]==root break    for i=0;i<pre.length;i++                if i<p            //中序左子树数组            inLeft[]=in[i]            //前序左子树数组            preLeft[]=pre[i+1]        else if i>p            //中序的右子树            inRight[]=in[i]            //前序的右子树            preRight[]=pre[i]    Node->left=reConstructBinaryTree(preLeft,inLeft)    Node->right=reConstructBinaryTree(preRight,inRight)    return Node

<?phpclass TreeNode{    var $val;    var $left = NULL;    var $right = NULL;    function __construct($val){        $this->val = $val;    }   };function reConstructBinaryTree($pre, $vin){        $len=count($pre);        if($len==0){                return null;        }           $root=$pre[0];        $node=new TreeNode($root);        for($p=0;$p<$len;$p++){                if($vin[$p]==$root){                        break;                }           }           $preLeft=array();        $preRight=array();        $vinLeft=array();        $vinRight=array();        for($i=0;$i<$len;$i++){                if($i<$p){                        $preLeft[]=$pre[$i+1];                        $vinLeft[]=$vin[$i];                }else if($i>$p){                        $preRight[]=$pre[$i];                        $vinRight[]=$vin[$i];                }           }           $node->left=reConstructBinaryTree($preLeft,$vinLeft);        $node->right=reConstructBinaryTree($preRight,$vinRight);        return $node;}$pre=array(1,2,4,7,3,5,6,8);$vin=array(4,7,2,1,5,3,8,6);$node=reConstructBinaryTree($pre,$vin);;var_dump($node);

object(TreeNode)#1 (3) {  ["val"]=>  int(1)  ["left"]=>  object(TreeNode)#2 (3) {    ["val"]=>    int(2)    ["left"]=>    object(TreeNode)#3 (3) {      ["val"]=>      int(4)      ["left"]=>      NULL      ["right"]=>      object(TreeNode)#4 (3) {        ["val"]=>        int(7)        ["left"]=>        NULL        ["right"]=>        NULL      }    }    ["right"]=>    NULL  }  ["right"]=>  object(TreeNode)#5 (3) {    ["val"]=>    int(3)    ["left"]=>    object(TreeNode)#6 (3) {      ["val"]=>      int(5)      ["left"]=>      NULL      ["right"]=>      NULL    }    ["right"]=>    object(TreeNode)#7 (3) {      ["val"]=>      int(6)      ["left"]=>      object(TreeNode)#8 (3) {        ["val"]=>        int(8)        ["left"]=>        NULL        ["right"]=>        NULL      }      ["right"]=>      NULL    }  }}

以上就是php如何实现根据前序和中序遍历结果重建二叉树（代码）的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的php如何实现根据前序和中序遍历结果重建二叉树（代码）全部内容，希望文章能够帮你解决php如何实现根据前序和中序遍历结果重建二叉树（代码）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。