PHP的二叉树

二叉树生成:

1.传进来一个值,当前二叉树对象没用值,放置一个值,

  1. 传进一个值,当前二叉树对象有值
  判断当前对象值和传进来的大小,如果传进来的值大,new 一个 self,放置到右边,然后调用 右边二叉树对象的 创建值的方法。
  判断当前对象值和传进来的大小,如果传进来的值小,new 一个 self,放置到左边,然后调用 左边二叉树对象的 创建值的方法。

下面这个例子,不能中途添加数据,只能一次生成,不能旋转,只是一个简单的demo,供大家借鉴。

例子:

/**
 * Btree 类
 */
class Btree
{
    private $key = 0;
    /** @var $left self */
    private $left;
    /** @var $right self */
    private $right;

    /**
     * 构造函数
     */
    public function __construct($arr = null)
    {
        $this -> _init($arr);
    }

    /**
     * 将数组初始化成二叉树
     *
     * @param $key
     *
     * @return bool
     */
    private function _init($key)
    {
        if (empty($key)) {
            return false;
        }
        if ( !is_array($key) && empty($this -> key)) {
            $this -> key = $key;
            return true;
        }
        foreach ($key as $k) {
            $this -> _create($k);
        }
        return true;
    }

    /**
     * 生成二叉树核心方法
     *
     * @param $key
     *
     * @return bool
     */
    private function _create($key)
    {
        if (empty($this -> key)) {
            $this -> key = $key;
            return true;
        }

        if ($this -> key > $key) {
            if (empty($this -> left)) {
                $this -> left = new self;
            }
            $this -> left -> _create($key);
        } else {
            if (empty($this -> right)) {
                $this -> right = new self;
            }
            $this -> right -> _create($key);
        }
        return true;
    }

    /**
     * 获取二叉树的升序排序
     *
     * @return array
     */
    public function up()
    {
        // 获取当前对象的 key 并变成数组,以统一返回类型
        $current = [$this -> key];
        if (empty($this -> left) && empty($this -> right)) {
//            如果没有 左子树 和 右子树,直接返回当前值的数组即可
            return $current;
        }
        if (empty($this -> left) && !empty($this -> right)) {
            /**
             * 如果没有左子树 并且有 右子树
             * 当前值 肯定比 右子树 所有的值 要小
             * 所以 把当前值放置在开始位置 连接数组后返回
             */
            return array_merge($current, $this -> right -> up());
        } else if (empty($this -> right) && !empty($this -> left)) {
            /**
             * 如果没有右子树 并且有 左子树
             * 当前值 肯定比 左子树 所有的值 要大
             * 所以 把当前值放置在结束位置 连接数组后返回
             */
            return array_merge($this -> left -> up(), $current);
        }
        /**
         * 当 既有左子树 又有 右子树时
         * 当前值 肯定比 左子树所有数值 要大
         * 当前值 肯定比 右子树所有数值 要小
         * 所以 连接数组的时候 左子树的 在前 当前的在中间 右子树的在右
         */
        return array_merge($this -> left -> up(), $current, $this -> right -> up());
    }

    /**
     * 获取二叉树的降序排序
     *
     * @return array
     */
    public function down()
    {
        $current = [$this -> key];
        if (empty($this -> left) && empty($this -> right)) {
            return $current;
        }
        if (empty($this -> left) && !empty($this -> right)) {
            return array_merge($this -> right -> down(), $current);
        } else if (empty($this -> right) && !empty($this -> left)) {
            return array_merge($current, $this -> left -> down());
        }
        return array_merge($this -> right -> down(), $current, $this -> left -> down());
    }
}

$arr = [5, 6, 4, 7, 2, 78, 12, 45, 23, 122, 786, 456, 237, 127, 1, 3];

$bt = new Btree($arr);

$up = $bt -> up();
$down = $bt -> down();

print_r($bt);

print_r($up);
print_r($down);

输出结果:

Btree Object
(
    [key:Btree:private] => 5
    [left:Btree:private] => Btree Object
        (
            [key:Btree:private] => 4
            [left:Btree:private] => Btree Object
                (
                    [key:Btree:private] => 2
                    [left:Btree:private] => Btree Object
                        (
                            [key:Btree:private] => 1
                            [left:Btree:private] => 
                            [right:Btree:private] => 
                        )

                    [right:Btree:private] => Btree Object
                        (
                            [key:Btree:private] => 3
                            [left:Btree:private] => 
                            [right:Btree:private] => 
                        )

                )

            [right:Btree:private] => 
        )

    [right:Btree:private] => Btree Object
        (
            [key:Btree:private] => 6
            [left:Btree:private] => 
            [right:Btree:private] => Btree Object
                (
                    [key:Btree:private] => 7
                    [left:Btree:private] => 
                    [right:Btree:private] => Btree Object
                        (
                            [key:Btree:private] => 78
                            [left:Btree:private] => Btree Object
                                (
                                    [key:Btree:private] => 12
                                    [left:Btree:private] => 
                                    [right:Btree:private] => Btree Object
                                        (
                                            [key:Btree:private] => 45
                                            [left:Btree:private] => Btree Object
                                                (
                                                    [key:Btree:private] => 23
                                                    [left:Btree:private] => 
                                                    [right:Btree:private] => 
                                                )

                                            [right:Btree:private] => 
                                        )

                                )

                            [right:Btree:private] => Btree Object
                                (
                                    [key:Btree:private] => 122
                                    [left:Btree:private] => 
                                    [right:Btree:private] => Btree Object
                                        (
                                            [key:Btree:private] => 786
                                            [left:Btree:private] => Btree Object
                                                (
                                                    [key:Btree:private] => 456
                                                    [left:Btree:private] => Btree Object
                                                        (
                                                            [key:Btree:private] => 237
                                                            [left:Btree:private] => Btree Object
                                                                (
                                                                    [key:Btree:private] => 127
                                                                    [left:Btree:private] => 
                                                                    [right:Btree:private] => 
                                                                )

                                                            [right:Btree:private] => 
                                                        )

                                                    [right:Btree:private] => 
                                                )

                                            [right:Btree:private] => 
                                        )

                                )

                        )

                )

        )

)
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 12
    [8] => 23
    [9] => 45
    [10] => 78
    [11] => 122
    [12] => 127
    [13] => 237
    [14] => 456
    [15] => 786
)
Array
(
    [0] => 786
    [1] => 456
    [2] => 237
    [3] => 127
    [4] => 122
    [5] => 78
    [6] => 45
    [7] => 23
    [8] => 12
    [9] => 7
    [10] => 6
    [11] => 5
    [12] => 4
    [13] => 3
    [14] => 2
    [15] => 1
)

可能会有问题,欢迎指正。 不要问我怎么写的博客。请直接告诉我你想说啥。 程序员吗 弯弯绕很烦人。

阿杰博客
请先登录后发表评论
  • latest comments
  • 总共0条评论