画江湖之数据结构 [第三话:二叉树] 二茶🌲

Krisji 的个人博客 / 1075 / 0 / 创建于 5年前 / 更新于 5年前

二叉树

1 二叉树简介

概括：

二叉树是每个结点最多有两个子树的树结构

二叉树的遍历

二叉树遍历的定义：按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。

先序遍历(DLR) 根左右 preOrder

中序遍历(LDR) 左根右 inOrder

后序遍历(LRD) 左右根 postOrder

2 以下介绍上述三种遍历二叉树的简介

DLR（先序遍历）、LDR（中序遍历）、LRD（后序遍历）

1. 先序遍历结果为: 8 3 1 6 4 7 10 14 13

2. 中序遍历结果为: 1 3 4 6 7 8 10 13 14

3. 后序遍历结果为: 1 4 7 6 3 13 14 10 8

完整代码块：

<?php 

//
//                   8
//                 /   \
//                3     10
//               / \      \
//              1   6      14
//                 / \     /
//                4   7   13 
//

class tree{
    public $data;
    public $left =  null ;
    public $right = null;
    public function __construct($data){
        $this->data = $data;
    }

    // DLR
    public function preOrder(){
        echo $this->data." ";
        if($this->left)
            $this->left->preOrder();
        if($this->right)
            $this->right->preOrder();
    }
    // LDR
    public function inOrder(){
        if($this->left)
            $this->left->inOrder();
        echo $this->data." ";
        if($this->right)
            $this->right->inOrder();
    }
    // LRD
    public function postOrder(){
        if($this->left)
            $this->left->postOrder();
        if($this->right)
            $this->right->postOrder();
        echo $this->data." ";
    }
}

$trees = new tree(8);
$trees->left =  new tree(3);
$trees->left->left =  new tree(1);
$trees->left->right = new tree(6);
$trees->left->right->left = new tree(4);
$trees->left->right->right = new tree(7);

$trees->right =  new tree(10);
$trees->right->right = new tree(14);
$trees->right->right->left =  new tree(13);

echo "<pre>";
$trees->preOrder();
echo "<br>";
$trees->inOrder();
echo "<br>";
$trees->postOrder();
echo "<br>";

3 分析代码块具体分析到代码注释哦～

先定义树的结构属性

class tree{
    public $data;
    public $left =  null ;
    public $right = null;
    public function __construct($data){
        $this->data = $data;
    }

先序遍历（顺序为根左右）

// DLR 先序遍历（根左右）
    public function preOrder(){
        echo $this->data." ";//先输出根节点 8 3 1
        if($this->left)//如果这个根节点有左子树
            $this->left->preOrder();//递归输出左子树 3 4
        if($this->right)//如果这个子节点有右子树 3
            $this->right->preOrder();//递归输出右子树 6 7

    }
    $trees->preOrder();

中序遍历（顺序为左根右）

// LDR 中序遍历（左根右）
public function inOrder(){
if($this->left)//先递归遍历左边的树
$this->left->inOrder();
echo $this->data." ";//输出中间的树
if($this->right)//再递归遍历右边的树
$this->right->inOrder();
}

后序遍历（顺序为左右根）

// LRD 后序遍历（左右根）
public function postOrder(){
if($this->left)//先递归遍历左边的树
$this->left->postOrder();
if($this->right)//再递归遍历右边的树
$this->right->postOrder();
echo $this->data." ";//最后输出根
}

php 数据结构