树和二叉树(一)

树和二叉树(一)

树结构

树型结构是一类非常重要的非线性数据结构,其中以树和二叉树最为常用 .
树 是由n(n>=1)个有限节点组成一个具有层次关系的集合。它具有以下特点:每个节点有零个或多个子节点;没有父节点的节点称为 根 节点;每一个非根节点有且只有一个 父节点 ;除了根节点外,每个子节点可以分为多个不相交的子树。 

undefined

其中的每个元素叫做节点。树的顶点(没有父元素的节点)叫根节点,如 E;每个分支的末端节点(没有子元素的节点)叫叶子节点,如 G、H、I、J、K、L;用来连接相邻节点之间的关系叫父子关系,比如 E 是 A、F 的父节点,A、F 是 E 的子节点;具有同一个父节点的多个子节点叫做兄弟节点,比如 A、F 是兄弟节点。
节点拥有的子节点数目叫做节点的度,显然,叶子节点的度为 0,树的度是树内各节点度的最大值。

除此之外,树还有高度、深度和层的概念:

undefined


undefined

注:其实线性表也可以看作一种特殊的树,只不过所有节点都在一个分支上,第一个元素是根节点,最后一个元素是子节点,没有兄弟节点。层数就是线性表的长度。

二叉树

二叉树是我们平时遇到的最常见的树结构,它是一种特殊的树,顾名思义,就是每个节点最多有两个「分叉」,即两个子节点,分别是左子节点和右子节点,不过,二叉树并不要求每个节点都有两个子节点,有的节点只有左子结点,有的节点只有右子节点。


这几种都是二叉树

满二叉树和完全二叉树:

根据左右子节点的饱和度,我们又从二叉树中提取出两种特殊的二叉树——满二叉树和完全二叉树。满二叉树即所有分支节点都有左右子节点,并且所有叶子节点都在同一层上,如上面的图2便是满二叉树。完全二叉树即除了最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。比如上面的图3就是完全二叉树.

总结:

满二叉树一定是完全二叉树,完全二叉树不一定满二叉树。

i  层上至多有2^(i-1)个结点。(i>=1)

深度为 k  的二叉树至多有 2^k - 1个结点(k>=1)

若(度为0)终端结点数为n0,度为2的结点数为n2,则n0=n2+1

具有n个结点的完全二叉树的深度为[log2n]+1(不大于log2n的最大整数,向下取整的意思)

对一棵有n个结点的完全二叉树(深度为[log2n]+1),按层编号,每层从左往右,对任意结点 i :
     若i=1,结点i为二叉树的跟;若i>1,其双亲为 [ i/2 ](取整)
    若2i>n,则结点i无左孩子,否则左孩子为2i
    若2i+1>n,则结点无右孩子,否则右孩子为 2i+1

二叉树可以通过数组和链表进行存储

数组


我们按照从上到下,从左到右对所有节点编号,可以看到,下一层的左右子节点和对应父节点序号存在某种数学关系,如果父节点的序号是 i,其对应左子节点位于 2i 的位置上,对应右子节点位于 2i + 1 的位置上,我们可以参照这个规则将上述完全二叉树存储到数组中.


那么其它二叉树怎么弄呢?,我们把不存在的节点补全,比如假设上述序号为 4、6、8、9 的元素不存在:


可以看到,我们将不存在的元素补上,只是对应位置值为 null,缺失的节点越多,数组的「空洞」也就越多,如果是极端情况,比如二叉树只包含 1、3、7 三个元素,那么数组中将会存在大量的「空洞」,浪费大量的空间,而且也会影响性能。
综上,数组适合满二叉树、完全二叉树这些特殊二叉树的存储,一些比较稠密的二叉树也可以用数组,如果二叉树比较稀疏就不适合用数组了,

链表

理论上来说,链表适用于所有的二叉树存储,只不过这里我们需要对线性表中的链表进行扩展,因为二叉树特定节点最多有两个子节点,所有我们在链表结点上设置两个指针域,分别指向左右子节点,所以这种链表结构又被称作二叉链表。我们可以通过一个类表示二叉链表的结点:
class Node
{
public $data;
public $left = null;
public $right = null;

public function __construct($data)
{
$this->data = $data;
}
}
如果要用二叉链表表示上面的完全二叉树,对应的图示如下


不管是什么样结构的二叉树,用链表来存储都不会存在空间的浪费。