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

二叉树

1 二叉树简介

概括:

  • 二叉树是每个结点最多有两个子树的树结构
    file
  • 二叉树的遍历
  • 二叉树遍历的定义:按照一定的规律不重复地访问(或取出结点中的信息,或对结点作其它的处理)二叉树中的每一个结点。

    1. 先序遍历(DLR) 根左右 preOrder
    2. 中序遍历(LDR) 左根右 inOrder
    3. 后序遍历(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

file

完整代码块

<?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
Krisji
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!