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 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

全排列生成算法:next_permutation

概念 全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则...

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

P1146 硬币翻转

题目描述 在桌面上有一排硬币,共N枚,每一枚硬币均为正面朝上。现在要把所有的硬币翻转成反面朝上,规则是每次可翻转任意N-1枚硬币(正面向上的被翻转为反面向上,反...

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

洛谷P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

33311
来自专栏顶级程序员

判断链表是否有环

判断一个单向链表是否有环。(指向表头结点的指针为head) 方法一: (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head (2)p1和p2分别...

4407
来自专栏彭湖湾的编程世界

【算法】赫夫曼树(Huffman)的构建和应用(编码、译码)

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

3455
来自专栏开源优测

Python3快速排序

Python3快速排序 概述 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。 通过一趟排序将要...

3186
来自专栏Bingo的深度学习杂货店

Q111 Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

2504
来自专栏趣谈编程

快速排序(基础版)

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

2144 砝码称重 2

 时间限制: 1 s  空间限制: 16000 KB  题目等级 : 钻石 Diamond 题解 题目描述 Description 有n个砝码,现在要称一个质量...

3456
来自专栏Android机动车

数据结构——遍历二叉树

二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

611

扫描关注云+社区