PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构

(原创内容,转载请注明来源,谢谢)

一、树的含义

1、树为非线性结构,是n(n>=0)个节点的有限集,非空树有一个根节点,n>1时有m(m>0)个互不相交的子树。

2、树的节点包含一个数据元素及若干指向其他节点的分支,节点拥有子树的数目称为树的度,度为0的节点称为叶子或终端节点,度不为0的节点称为非终端节点或分支节点。树的度为各节点度的最大值。

3、节点的子树称为节点的孩子,节点称为孩子的双亲,同一个双亲的节点称为兄弟,节点的祖先为从根到该节点所经分支上的所有节点。根的子树中任一节点称为子孙。

4、节点层次从根算起,根为第一层。双亲在同一层节点的互为堂兄弟。节点最大的层次称为节点的深度。各子树从左到右有秩序,则成为有序树,否则为无序树。

5、森林是m(m>=0)棵互不相交的树的集合。对于树的每个节点,其子树的集合即为森林。

二、二叉树

1、二叉树是一种树型结构,每个节点至多有两个子树,且有左右之分,次序不能颠倒,是有序树。

2、根据二叉树的定义,其有五种形态:空树、仅有根的树、有根及左节点、有根及右节点、有根及两个节点。

3、二叉树具有五个性质

1)在二叉树的第i层,至多有2i-1个节点,i>=1

2)深度为k的二叉树,至多有2k-1个节点,k>=1

3)对任一棵二叉树,假设终端节点数目为a,度为2的节点数为b,则a=b+1

4)具有n个节点的完全二叉树,深度为(log2n)+1,其中log2n的值向下取整

5)如果一棵有n个节点的完全二叉树,对任意第i个节点(1<=i<=n)

A. 如果i=1,则节点i是二叉树的根,无双亲;i>1,则双亲节点的序号为i/2的结果向下取整

B. 如果2i>n,则节点i无左孩子,否则左孩子的节点是2i

C. 当2i+1>n,则节点i无右孩子,否则右孩子的节点是2i+1

4、满二叉树概念:深度为k,且有2k-1个节点。

5、完全二叉树概念:深度为k,有n个节点,当且仅当每个节点都与深度为k的满二叉树从1至n的编号一一对应。

6、二叉树的存储结构

1)顺序结构:用一组连续的存储空间保存二叉树,按照完全二叉树的定义对每个节点进行存储,不是完全二叉树的则需要相应的位置留空。因此该方案仅适用于完全二叉树,非完全二叉树用该方式存储会浪费大量存储空间。

2)链式结构:二链表方式(数据域、左指针、右指针),三链表方式(二链表+父指针)。该方式存储时,n个节点的二叉链表,有n+1个空链域。

三、线索二叉树

1、定义:在链式二叉树的基础上进行改动。当链式二叉树某个节点的左指针没有指向时,其指向该节点的前驱,相对应的右指针指向后继。

2、结构:为了区分指针是指向前驱/后继还是指向子节点,需要增加两个标志域,分别表示其左/右节点指向子节点还是指向前驱/后继。总体结构包含:左指针、左标志域、数值、右标志域、右指针。

四、遍历二叉树

1、定义:沿某路径逐个访问每个节点,使每个节点均被访问正好一次。

2、三种遍历方式

1)先序遍历:先遍历根节点,再遍历左节点,最后遍历右节点。

2)中序遍历:先遍历左节点,再遍历根节点,最后遍历右节点。

3)后序遍历:先遍历左节点,再遍历右节点,最后遍历根节点。

3、对二叉树进行遍历,本质是将非线性结构的二叉树进行线性化,使每个节点至多一个前驱与一个后继。

4、用PHP遍历二叉树

二叉树结构如图:

代码执行结果如图:

源码如下:

<?php
//线索二叉树
class Node{
         public$left = null;
         public$right = null;
         public$data = null;
}
///先序遍历——根->左->右
function preSearch($root){
         $nodeStack= array();
         $resultDataStack= array();
         $resultNodeStack= array();
         array_push($nodeStack,$root);
         while(!empty($nodeStack)){
                   //array_pop为后进先出,是栈的数据结构
                   $node= array_pop($nodeStack);//每次while循环,相当于获取一个子树的根
                  array_push($resultDataStack,$node->data);
                   array_push($resultNodeStack,$node);
                   //先把右节点压进栈,后压左节点
                   //则下个循环的pop会先把左边节点弹出,以达到先左后右的目的
                   if($node->right!= null){
                            array_push($nodeStack,$node->right);
                   }
                   if($node->left!= null){
                            array_push($nodeStack,$node->left);
                   }       
         }
         returnarray('data'=>$resultDataStack,'node'=>$resultNodeStack);
}
//中序遍历——左->根->右
function centerSearch($root){
         $nodeStack= array();
         $resultDataStack= array();
         $resultNodeStack= array();
         $centerNode= $root;
         while(!empty($nodeStack)|| $centerNode!=null){
                   while($centerNode!= null){
                            //对于每个节点,先把其压进栈,再不断遍历其左节点
                            //以达到从左节点开始遍历的目的
                            array_push($nodeStack,$centerNode);
                            $centerNode= $centerNode->left;
                   }
                   //上面while弹出,相当于取到每个子树的最左边的子树节点的下一个位置(null)
                   //由于其是null,表面该子树没有左节点,则此子树为本次遍历的最左节点
                   //因此需要回滚(pop)
                   $centerNode= array_pop($nodeStack);
                   array_push($resultDataStack,$centerNode->data);
                   array_push($resultNodeStack,$centerNode);
                   //取此根的右节点,并进入下次循环,继续找该节点的最左节点
                   $centerNode= $centerNode->right;
         }
         returnarray('data'=>$resultDataStack,'node'=>$resultNodeStack);    
}
//后序遍历——左->右->根
function backSearch($root){
         $nodeStack= array();
         $assistStack= array();//需要借助辅助栈
         $resultDataStack= array();
         $resultNodeStack= array();
         array_push($nodeStack,$root);
         while(!empty($nodeStack)){
                   $node= array_pop($nodeStack);
                   //把弹出的node压入辅助栈
                   array_push($assistStack,$node);
                   //先压左边后压右边,这样下一轮循环的时候会先弹出右边的node
                   //以便把右边的node先压入最终的辅助栈
                   if($node->left!= null){
                            array_push($nodeStack,$node->left);
                   }
                   if($node->right!= null){
                            array_push($nodeStack,$node->right);
                   }                
         }
         while(!empty($assistStack)){
                   $node= array_pop($assistStack);
                   array_push($resultDataStack,$node->data);
                   array_push($resultNodeStack,$node);          
         }
         returnarray('data'=>$resultDataStack,'node'=>$resultNodeStack);    
}
$a = new Node(); 
$b = new Node(); 
$c = new Node(); 
$d = new Node(); 
$e = new Node(); 
$f = new Node(); 
$a->data = '1'; 
$b->data = '2'; 
$c->data = '3'; 
$d->data = '4'; 
$e->data = '5'; 
$f->data = '6'; 
$a->left = $c; 
$a->right = $b; 
$b->left = $f; 
$c->left = $e; 
$c->right = $d; 
$res = preSearch($a);
echo '先序遍历的结果是:';
print_r($res['data']);
echo '<br />';
$res = centerSearch($a);
echo '中序遍历的结果是:';
print_r($res['data']);
echo '<br />';
$res = backSearch($a);
echo '后序遍历的结果是:';
print_r($res['data']);
echo '<br />';

——written by linhxx 2017.06.29

相关阅读:

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-06-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

2712
来自专栏nnngu

数据结构08 线索二叉树

上一篇总结了二叉树,这一篇要总结的是线索二叉树,我想从以下几个方面进行总结。 1、什么是线索二叉树? 2、为什么要建立线索二叉树? 3、如何将二叉树线索化? 4...

3176
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

1877
来自专栏我的技术专栏

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

1124
来自专栏数据结构与算法

codevs 1814 最长链

1814 最长链 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 现给出...

2845
来自专栏Java Edge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

1432
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

1906
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

1302
来自专栏令仔很忙

集合详解(二)----ArrayList源代码剖析(JDK1.7)

ArrayList是List类的一个典型的实现,是基于数组实现的List类,因此,ArrayList封装了一个动态的、可变长度的Object[]数组。Arra...

571
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

852

扫码关注云+社区