利用PHP实现常用的数据结构之二叉树（小白系列文章五）

developerworks 发布于2019-06-27 16:27 / 977人阅读

摘要：回来更新一波，最近刷剑指，才又发现树真是一个大头，二叉树的题目和变化运用好多啊二叉树算法引子很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书

回来更新一波，最近刷《剑指offer》，才又发现树真是一个大头，二叉树的题目和变化运用好多啊～

/**
*    PHP二叉树算法
*    Created on 2017-5-6
*   Update  on 2017-8-10
*    Author     entner
*    Email     1185087164@qq.com
*/

引子

很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎；还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书的价值，要多读几本才会把你和别人的差别体现出来。
二叉树是严格定义的，有很好的对称性和比较高的数据关联度，对数据的存储和计算，有很好的演示作用，比如完全二叉树：

当然，二叉树更适合链表存储，效率更高，总的来说，以二叉树为基础我们可以衍生出许多神奇的运用，举几个常用的场景为我说的话正言：

编译器表达式处理

快速查找与排序

文件压缩

文件系统管理

游戏场景划分、监测、渲染

 我承认，上面好多东西你并不会直接接触，但是，我们关键是去学习一种思维和设计，退一万步也可以增加一点见识：）

一、二叉树抽象数据类型操作条目

关于书的操作太多了，我只列一些常用的(这些都是常考的知识点)，有兴趣的相信也有技能去淘到“好货”

 -InitTree    构造空树
 -PreTra    返回树中某结点的值
 -InTra        给树中某结点赋值为value
 -LevelTra     返回某非根结点的双亲，否则返回空
 -LeftChild  返回某非叶结点的最左孩子，否则返回空

二、默写二叉树常用数据结构

默写会让你记忆更深刻，同时也会锻炼抽象的逻辑思维，一边看不懂，就多看几遍，再查一查相关资料，应该问题不大，你甚至可以找张纸默写一下。

/**     
*InitTree 初始化树
*    
*
    Typedef int TElementType //构造一个数据类型
    Typedef Struct Tree{    //构造二叉树抽象数据类型
        TElementType data;    //声明一个数组，先构建一个树
        Struct Tree *leftChild;    //左孩子节点
        Struct Tree *rightChild;   //右孩子节点
    }Tree;
*／

/**
 * Value     获取树的结点(前序遍历)
 * Return   返回获取的结点值
     Status Value（Tree *T，int e）{
        if(T == null){
            return error;
        }
        e = T->Value(T->leftChild);
        e = T->Value(T->rightChild);
        return e;
     }
 */

/**
 * Assign     给树中某结点赋值为v(前序遍历)
 * Return   返回赋值后的结点值
     Status Assign（Tree *T，int e, TElementType v）{
        if(T == null){
            return error;
        }
        e = T->Assign(T->leftChild);
        e = T->Assign(T->rightChilg);
        e = v;
        return e;
     }
 */

三、二叉树结构基本实现

/**
*    PHP二叉树算法
*    Created on 2017-8-7
*    Author     entner
*    Email     1185087164@qq.com
*/

/*
    假设我构造一颗如下的二叉树
            A
        B       C
      #   D   #   # 
        #   #
*/

error_reporting(E_ALL ^ E_NOTICE);

$data = array(
        0=>"A",
        1=>"B",
        2=>"#",
        3=>"D",
        4=>"#",
        5=>"#",
        6=>"C",
        7=>"#",
        8=>"#",
    );

Class BTNode{
    public $data;
    public $lChild;    
    public $rChild;

    public function __construct($data = null){
        $this->data = $data;
    }
}

Class BinaryTree{

    public $root;
    public $btData;

    public function __construct($data = null){
        $this->root = null;
        $this->btData = $data;
        //$this->preOrderCreateBT($this->root);
    }

    public function preOrderCreateBT(&$root = null){
        $elem = array_shift($this->btData);    //移除数组头部，并作为结果返回
        if($elem == null){    #判断：当数组为空时    
            return ;
        }else if($elem == "#"){    #判断：当数组为无效单元时，该节点是虚节点，退出当前递归，执行下一个递归
            $root = "#";
            return $root;
        }else{
            $root = new BTNode();
            $root->data = $elem;
            $this->preOrderCreateBT($root->lChild);
            $this->preOrderCreateBT($root->rChild);
        }
        return $root;
    }


    /**
     * TODO:先序遍历二叉树
     * @param $tree object 二叉树
     * @param $temp array  二叉树输出节点存储数组
     */
    public function printBTPreOrder($tree,&$temp){
        if($tree != null){
            $temp[] = $tree->data;
            $this->printBTPreOrder($tree->lChild,$temp);
            $this->printBTPreOrder($tree->rChild,$temp);
        }else{
            return ;
        }
        return $temp;
    }

    /**
     * TODO:中序遍历二叉树
     * @param $tree object 二叉树
     * @param $temp array  二叉树输出节点存储数组
     */
    public function printBTInOrder($tree,&$temp){
        if($tree != null){
            $this->printBTInOrder($tree->lChild,$temp);
            $temp[] = $tree->data;
            $this->printBTInOrder($tree->rChild,$temp);
        }else{
            return;
        }
        return $temp;
    }

    /**
     * TODO:中序遍历二叉树
     * @param $tree object 二叉树
     * @param $temp array  二叉树输出节点存储数组
     */
    public function printBTPosOrder($tree,&$temp){
        if($tree != null){
            $this->printBTPosOrder($tree->lChild,$temp);
            $this->printBTPosOrder($tree->rChild,$temp);
            $temp[] = $tree->data;
            
        }else{
            return;
        }
        return $temp;
    }

    /**
     * TODO:层序遍历二叉树（需要将书中节点放入队中）
     * 
     */
    function PrintFromTopToBottom(&$root)
    {
        // write code here
        if($root == null){
            return ;
        }
        $queue = array();
        array_push($queue,$root);
        
        while(!is_null($node = array_shift($queue))){
            echo $node->data . " ";
            if($node->left != null){
                array_push($queue,$node->lChild);

            }
            if($node->left != null){
                array_push($queue,$node->rChild);
            }
        }
    }

}


$object = new BinaryTree($data);
$tree = $object->preOrderCreateBT($root);

echo "";
print_r($tree);die;
四、二叉排序树
/**
*FindBitTree      二叉树查找
*@param T BItTree 代指二叉树及其元素结点
*@param key int   树中某结点
*@param f   point 指向该结点父结点
*@param p   point 指向该元素结点或空
*@param return bool true|false
   status SearchBST(BitTree T,int key,BitTree f = null,BitTree p){
        if(!T){
            p = f;
            return false;
        }
        if(key == T->data){
            p = T；//其实就是根结点
            return true；
        }else if(key data){
            SearchBST(T->lChild,int key,T,p);
        }else if(key >T->data){
            SearchBST(T->rChild,int key,T,p);
        }
   }
*/

/**
InsertBitTree      二叉树插入 
*【如果当前树中没有key元素，则插入，插入的结点一定是叶子结点】
*@param T BItTree 代指二叉树及其元素结点
*@param key int   树中某结点
*@param return bool true|false
   status InsertBST(BitTree T，int key){
        if(SearchBST(T,key,NULL,&p) == false){
            s->data = key;
            s->lChild = s->rChild = NULL;
            if(!p){
                T= s;
            }else if(key < p->data){
                p->lChild = s;
            }else{
                p->rChild = s;
            }
          return true;
        }
        return false;
   }
*/
五、树应用实现-无限极分类（引用&递归）
$items = array(
    1 => array("id" => 1, "pid" => 0, "name" => "江西省"),
    2 => array("id" => 2, "pid" => 0, "name" => "黑龙江省"),
    3 => array("id" => 3, "pid" => 1, "name" => "南昌市"),
    4 => array("id" => 4, "pid" => 2, "name" => "哈尔滨市"),
    5 => array("id" => 5, "pid" => 2, "name" => "鸡西市"),
    6 => array("id" => 6, "pid" => 4, "name" => "香坊区"),
    7 => array("id" => 7, "pid" => 4, "name" => "南岗区"),
    8 => array("id" => 8, "pid" => 6, "name" => "和兴路"),
    9 => array("id" => 9, "pid" => 7, "name" => "西大直街"),
    10 => array("id" => 10, "pid" => 8, "name" => "东北林业大学"),
    11 => array("id" => 11, "pid" => 9, "name" => "哈尔滨工业大学"),
    12 => array("id" => 12, "pid" => 8, "name" => "哈尔滨师范大学"),
    13 => array("id" => 13, "pid" => 1, "name" => "赣州市"),
    14 => array("id" => 14, "pid" => 13, "name" => "赣县"),
    15 => array("id" => 15, "pid" => 13, "name" => "于都县"),
    16 => array("id" => 16, "pid" => 14, "name" => "茅店镇"),
    17 => array("id" => 17, "pid" => 14, "name" => "大田乡"),
    18 => array("id" => 18, "pid" => 16, "name" => "义源村"),
    19 => array("id" => 19, "pid" => 16, "name" => "上坝村"),
);

/**
*TODO:通过引用方式实现无限极分类
*    
*/
function tree_Classify1($items){
    $tree=array();
    $packData=array();
    foreach ($items as  $data) {
        $packData[$data["id"]] = $data;
    }
    foreach ($packData as $key =>$val){     
        if($val["pid"]==0){//代表跟节点       
            $tree[]=& $packData[$key];
        }else{
            //找到其父类
            $packData[$val["pid"]]["son"][]=& $packData[$key];
        }
    }
    return $tree;
}

/**
*TODO:通过递归方式实现无限极分类
*      
*/
function tree_Classify2($items,$child="_child",$root = 0){
    $tree=array();
    foreach($items as $key=> $val){

        if($val["pid"]==0){
            //获取当前$pid所有子类 
                unset($items[$key]);
                if(! empty($items)){
                    $child=make_tree1($items,$child,$val["id"]);
                    if(!empty($child)){
                        $val["_child"]=$child;
                    }                   
                }              
                $tree[]=$val; 
        }
    }   
    return $tree;
}

echo "";
print_r(make_tree1($items,$child="_child",$root=0));
``

超融合服务器混合云实现二叉树二叉树的存储结构二叉树 php 二叉树 php

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/22923.html

利用PHP实现常用的数据结构之二叉树（小白系列文章六）

摘要：回来更新一波，最近刷剑指，才又发现树真是一个大头，二叉树的题目和变化运用好多啊二叉树算法引子很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书回来更新一波，最近刷《剑指offer》，才又发现树真是一个大头，二叉树的题目和变化运用好多啊～ /** * PHP二叉树算法 * Create...

Cympros 2019-06-28 13:56 评论0 收藏0
学习数据结构与算法之二叉搜索树

摘要：二叉搜索树是二叉树的一种，其特征是左侧子节点存储比父节点小的值，右侧子节点存储比父节点大或等于父节点的值。实现和这个两个方法其实挺简单的，最小的节点就在二叉搜索树的最左反之，最大的就在最右。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构...

denson 2019-08-21 11:54 评论0 收藏0
【数据结构初阶之二叉树】：二叉树相关的性质和经典的习题（用C语言实现，附图详解）

摘要：当集合为空时，称该二叉树为空二叉树。也就是说，如果一个二叉树的层数为，且结点总数是，则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。 ...

Martin91 2021-11-24 09:39 评论0 收藏0
PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。开篇以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。回顾 showImg(https://user-...

li21 2019-07-01 10:26 评论0 收藏0
数据结构之二叉树（java版）

摘要：二叉树是数据结构中很重要的结构类型，学习数据结构也是深入学习编程的必由之路，这里我们简单介绍下我对于二叉树的理解，水平有限，如有错误还请不吝赐教。二叉树是数据结构中很重要的结构类型，学习数据结构也是深入学习编程的必由之路，这里我们简单介绍下我对于二叉树的理解，水平有限，如有错误还请不吝赐教。首先照例定义一个二叉树的节点类 class Node { private int ...

JayChen 2019-08-14 18:02 评论0 收藏0