数据结构-二叉树

标签: 二叉树

二叉树的生成及前序、中序和后序遍历


这里写图片描述

<?php
    /**
     * 节点
     */
    class Node
    {
        public $node;//节点
        public $leftChild;//左孩子
        public $rightChild;//右孩子
        public function __construct($node)
        {
            $this->node = $node;
            $this->leftChild = '';
            $this->rightChild = '';//默认是空
        }
    }

    /**
    * 二叉树
    */
    class Btree 
    {
        public $root = '';//子树,在此基础上扩展二叉树

        static function index()
        {
            echo '';
        }

        /**
         * [insertNode 插入节点]
         * @param  [type] $child [需要插入的数据元素,还不是节点]
         * @return [type]        [description]
         */
        public function insertNode($child)
        {
            $newNode = new Node($child);//转换成子树
            if ($this->root == null) {//如果没有子树,把第一个子树赋值给根子树
                $this->root = $newNode;
            }else{
                $this->getInsertTree($this->root,$newNode);
            }

        }

        /**
         * [getInsertTree 遍历插入,形成二叉树,(已存在根节点)]
         * @param  [type] $parent  [根子树]
         * @param  [type] $child [新插入的子树,如果新子树的节点小于根子树的节点,则和根子树的左孩子比较,如果大于则和根子树的右孩子比较]
         * @return [type]        [description]
         */
        public function getInsertTree($parent,$child)
        {

            if (isset($child->node) && isset($parent->node)) {
                if ($child->node<$parent->node) {//如果节点小于根节点,看根节点的左孩子是否存在

                    if ($parent->leftChild == null) {//如果左孩子不存在

                        $parent->leftChild = $child;

                    }else{

                        $this->getInsertTree($parent->leftChild,$child);
                    }
                }else{
                    //如果大于等于根节点
                    if ($parent->rightChild == null) {//如果没有右孩子,把新节点放到右边
                        $parent->rightChild = $child;

                    }else{

                        $this->getInsertTree($parent->rightChild,$child);
                    }
                }
            }


        }

        /**
         * [getPreorder 前序遍历,根->左->右]
         * @param  [type] $tree [一棵树]
         * @return [type]       [description]
         */
        public function getPreorder($tree)
        {
            // print_r($tree);exit;//需要遍历的树
            if (isset($tree->node)) {//如果树存在
                echo $tree->node,'--';
                if(isset($tree->leftChild))//如果左孩子存在
                {
                    $this->getPreorder($tree->leftChild);
                }

                if(isset($tree->rightChild))//如果右孩子存在
                {
                    $this->getPreorder($tree->rightChild);
                }
            }

        }

        /**
         * [getMiddelorder 中序遍历,左->根->右,首先要遍历二叉树的左子树,接着遍历根节点,最后遍历右子树。如果子节点下边还有子节点也是按照左根右的顺序]
         * @param  [type] $tree [一棵树]
         * @return [type]       [description]
         */
        public function getMiddelorder($tree)
        {
            if (isset($tree->node)) {
                if (isset($tree->leftChild)) {//如果有左孩子则遍历
                    $this->getMiddelorder($tree->leftChild);
                }
                echo $tree->node,'--';
                if (isset($tree->rightChild)) {//如果有右孩子则遍历
                    $this->getMiddelorder($tree->rightChild);
                }
            }
        }

        /**
         * [getPostorder 后序遍历,左->右->根,首先按照后序遍历的规则遍历左子树,接着按照后序遍历的规则遍历右子树,最后访问根节点。]
         * @param  [type] $tree [description]
         * @return [type]       [description]
         */
        public function getPostorder($tree)
        {
            if (isset($tree->node)) {
                if (isset($tree->leftChild)) {
                    $this->getPostorder($tree->leftChild);
                }
                if (isset($tree->rightChild)) {
                    $this->getPostorder($tree->rightChild);
                }
                echo $tree->node,'--';
            }


        }
    }

    $nodes = [34,2,111,43,12,32,234,42,321,24,24,53];
    $bTree = new Btree();//实例化对象
    foreach ($nodes as $node) {//循环调用插入方法
        $bTree->insertNode($node);//$node为数组中的元素
    }

    //前序遍历,根->左->右
    $bTree->getPreorder($bTree->root);//34--2--12--32--24--24--111--43--42--53--234--321--
    echo "<br>";
    //中序遍历,左->根->右
    $bTree->getMiddelorder($bTree->root);//2--12--24--24--32--34--42--43--53--111--234--321--
    echo "<br>";
    //后序遍历
    $bTree->getPostorder($bTree->root);//24--24--32--12--2--42--53--43--321--234--111--34--

    ?>
版权声明:本文为weixin_37301300原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_37301300/article/details/82500265

智能推荐

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

猜你喜欢

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...