PHP数据结构与算法:二叉树

Wesley13
• 阅读 775

一、定义

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree) 。

二、特性

  1. 在二叉树的第i层上至多有2^(i-1)个结点(i>0)
  2. 深度为k的二叉树至多有2^k - 1个结点(k>0)
  3. 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1
  4. 具有n个结点的完全二叉树的深度必为 log2(n+1)
  5. 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)
  • 完全二叉树

若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

PHP数据结构与算法:二叉树

  • 满二叉树

除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

PHP数据结构与算法:二叉树

三、遍历

树的遍历是树的一种重要的运算。我们把依次对树中每个结点访问一次且仅访问一次的运算称为_遍历(traversal)_。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归,广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

PHP数据结构与算法:二叉树

1.深度优先遍历

对于一颗二叉树,_深度优先搜索(Depth First Search)_是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。深度优先遍历有重要的三种方式,这三种方式常被用于访问树的节点,它们之间的不同在于访问每个节点的次序不同。

  • 先序遍历(preorder)

先序遍历中,我们先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树。

根节点->左子树->右子树

  • 中序遍历(inorder)

中序遍历中,我们递归使用中序遍历访问左子树,然后访问根节点,最后再递归使用中序遍历访问右子树。

左子树->根节点->右子树

  • 后序遍历(postorder)

后序遍历中,我们先递归使用后序遍历访问左子树和右子树,最后访问根节点。

左子树->右子树->根节点

2.广度优先遍历(层次遍历)

从树的根开始,从上到下、从左到右遍历整个树的节点。

四、PHP的实现

节点实现:

<?php

/**
 * 节点实现
 */
class Node
{
    /**
     * 节点值
     * @var
     */
    public $elem;

    /**
     * 左孩子
     * @var
     */
    public $lchild;

    /**
     * 右孩子
     * @var
     */
    public $rchild;

    /**
     * Node constructor.
     * @param $item
     */
    public function __construct($elem = -1,$lchild = null,$rchild =  null)
    {
        $this->elen = $elem;
        $this->lchild = $lchild;
        $this->rchild = $rchild;
    }
}

树的实现:

<?php

/**
 * 二叉树基本操作
 * 1.add(elem)       添加节点
 * 2.breadth()       层次遍历
 * 3.preorder(node)  先序遍历
 * 4.inorder(node)   中序遍历
 * 5.postorder(node) 后序遍历
 */
class Tree
{
    /**
     * 根节点
     * @var null
     */
    public $root;

    /**
     * Tree constructor.
     * @param null $root
     */
    public function __construct($root = null)
    {
        $this->root = $root;
    }

    /**
     * 节点添加
     * @param $elem
     * @return void
     */
    public function add($elem)
    {
        $node = new Node($elem);

        //若树是空的,则队根节点赋值
        if(is_null($this->root)){
            $this->root = $node;
            return;
        }

        $queue = [];
        array_push($queue,$this->root);

        //对已有节点进行层次遍历
        while($queue){
            //出队
            $cur = array_shift($queue);

            //左孩子处理
            if(is_null($cur->lchild)){
                $cur->lchild = $node;
                return;
            }else{
                array_push($queue,$cur->lchild);
            }

            //右孩子处理
            if(is_null($cur->rchild)){
                $cur->rchild = $node;
                return;
            }else{
                array_push($queue,$cur->rchild);
            }
        }

    }

    /**
     * 层次遍历
     * 从根开始,从上到下、从左到右遍历整个树的节点
     */
    public function breadth()
    {
        if(is_null($this->root)){
            return;
        }
        $queue = [$this->root];
        while ($queue){
            $cur = array_shift($queue);
            echo $cur->elem . '<br />';
            if(!is_null($cur->lchild)){
                array_push($queue,$cur->lchild);
            }
            if(!is_null($cur->rchild)){
                array_push($queue,$cur->rchild);
            }
        }
    }

    /**
     * 先序遍历
     * 根节点->左子树->右子树
     * @param Node $node
     */
    public function preorder($node)
    {
        if(is_null($node)){
            return;
        }
        echo $node->elem . '<br />';
        $this->preorder($node->lchild);
        $this->preorder($node->rchild);
    }

    /**
     * 中序遍历
     * 左子树->根节点->右子树
     * @param $node
     */
    public function inorder($node)
    {
        if(is_null($node)){
            return;
        }
        $this->inorder($node->lchild);
        echo $node->elem . '<br />';
        $this->inorder($node->rchild);
    }

    /**
     * 后序遍历
     * 左子树->右子树->根节点
     * @param $node
     */
    public function postorder($node)
    {
        if(is_null($node)){
            return;
        }
        $this->postorder($node->lchild);
        $this->postorder($node->rchild);
        echo $node->elem . '<br />';
    }

}

$tree = new Tree();
$tree->add(0);
$tree->add(1);
$tree->add(2);
$tree->add(3);
$tree->add(4);
$tree->add(5);
$tree->add(6);
$tree->add(7);
$tree->add(8);
$tree->add(9);

$tree->breadth();
//$tree->preorder($tree->root);
//$tree->inorder($tree->root);
//$tree->postorder($tree->root);
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
JAVA递归实现线索化二叉树
JAVA递归实现线索化二叉树基础理论首先,二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为:根节点左子树右子树中序遍历为:左子树根节点右子树后序遍历为:左子树右子树根节点(只要记住根节点在哪里就是什么遍历,且都是先左再右)线索化现在有这么一棵二叉树,它的数据结
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
菜园前端 菜园前端
1年前
什么是二叉树?
原文链接:什么是二叉树?树中每个节点最多只能有两个子节点,在JavaScript中一般都是通过Object来模拟二叉树。常用操作前序遍历中序遍历后序遍历前序遍历根左右。口诀:1.访问根节点2.对根节点的左子树进行前序遍历3.对根节点的右子树进行前序遍历通过
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这