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
相关阅读: