首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >PHP数据结构(六) ——树与二叉树之概念及存储结构

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

作者头像
用户1327360
发布2018-03-07 10:22:26
1.3K0
发布2018-03-07 10:22:26
举报
文章被收录于专栏:决胜机器学习决胜机器学习

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数据结构(一)——顺序结构线性表

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-06-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 决胜机器学习 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、树的含义
  • 二、二叉树
  • 三、线索二叉树
  • 四、遍历二叉树
  • PHP数据结构(六) ——数组的相乘、广义表
  • PHP数据结构(五) ——数组的压缩与转置
  • PHP数据结构(四) ——队列
  • PHP数据结构(三)——运用栈实现括号匹配
  • PHP数据结构(二)——链式结构线性表
  • PHP数据结构(一)——顺序结构线性表
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档