PHP 使用二叉树的先序和中序遍历结果构造二叉树

  • 内容
  • 评论
  • 相关
<?php
    #树节点
    class Node {
        public $data = null;
        public $parent = null;
        public $left = null;
        public $right = null;
    }

    #根据先序和中序遍历数组建立二叉树,注意是二叉树,不是二叉排序树,而且条件是树没有相同的值

    #思想是使用先序数组确定根节点,然后通过中序数组找到根节点的左右子树节点

    #@param pre 前序遍历数组
    #@param in 中序遍历数组
    #@param pre_s 对于前序数组的构建树开始坐标
    #@param pre_e 对于前序数组的构建树结束坐标
    #@param in_s 对于中序数组的构建树起始坐标
    #@param p 构建树的根节点的父节点
    function build_bt_prein($pre, $in, $pre_s, $pre_e, $in_s, $p) {
        $root = new Node();
        $root->parent = $p;
        $root->data = $pre[$pre_s]; #根节点数据在pre数组的第一位
        $root_inx = array_search($root->data, $in); #根节点在in数组中的坐标

        #我把左右子树的pre数组,in数组的开始结束坐标写出来,便于理解
        $pre_l_s = $pre_s + 1; #左子树在pre数组的开始坐标
        $pre_l_e = $pre_s + ($root_inx - $in_s); #左子树在pre数组的结束坐标,其中root_inx-in_s为左子树长度
        $pre_r_s = $pre_l_e + 1; #右子树开始坐标
        $pre_r_e = $pre_e; #右子树结束坐标
        $in_l_s = $in_s; #左子树在in数组开始坐标
        $in_r_s = $root_inx + 1; #右子树在in数组开始坐标

        #注意此处
        if ($pre_l_s <= $pre_l_e) $root->left = build_bt_prein($pre, $in, $pre_l_s, $pre_l_e, $in_l_s, $root);
        if ($pre_r_s <= $pre_r_e) $root->right = build_bt_prein($pre, $in, $pre_r_s, $pre_r_e, $in_r_s, $root);

        return $root;
    }

    #中序遍历
    function inorder_traverse($root) {
        if ($root->left != null) inorder_traverse($root->left);
        echo $root->data . " ";
        if ($root->right != null) inorder_traverse($root->right);
    }

    $pre = array(7, 10, 4, 3, 1, 2, 8, 11);  
    $in = array(4, 10, 3, 1, 7, 11, 8, 2); 
    // $pre = array(2, 7);  
    // $in = array(7, 2); 
    $root =  build_bt_prein($pre, $in, 0, count($pre) - 1, 0, null);
    inorder_traverse($root);
?>

评论

0条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注