参考文献

之前所看到的都是线性存储结构

而树是一种非线性的存储结构

存储的是具有一对多关系的数据元素的集合


几个需要知道的基本概念(其实都是离散的知识了)

结点:使用树结构存储的每一个数据元素都被称为一个结点

父节点(双亲结点):对于ABCD来说,A是BCD的父结点

子结点(孩子结点):对于ABCD来说,BCD是A的子结点

兄弟结点:对于BCD来说,他们三都有相同的父节点A,所以它们互为兄弟结点

根节点:每棵树都有且只有一个被称为根的结点,在图里A就是这个根节点

判断依据为,如果这个结点没有父节点那么就是根节点(只有一个)

叶子结点:如果这个节点没有任何子结点,那么此结点就是叶节点


子树和空树

子树:假如把B看作根节点,那么BEFKL同样也可以视作为一棵树(当然不是真正的树)

我们称这样的‘树’为子树,同时可以引申出树的另一个定义:由根节点和若干棵子树构成

空树:如果集合为空,那么构成的树就被称为空树


结点的度和层次

度:对于一个结点,拥有的子树数(结点的分支有多少)称为结点的度

例如在这里A的度就是3,也就是说A有三棵子树

层次:从一棵树的树根开始,树根所在的层为第一层,以此类推

深度:一棵树最大的层次就是树的深度(高度),例如上图深度为4


有序树和无序树

如果树从左到右看或者从右到左看谁在左边谁在右边是固定的有规定的

那么这棵树就是有序树,反之为无序树

在有序树中,最左边的子结点通常被称为“第一个孩子”

最右边的子结点通常被称为“最后一个孩子”


森林

由m(m>0)个互不相交的树组成的集合被称为森林,例如图中A的三个子树就构成了森林


树的其它表示方法

图 2(A)是以嵌套的集合的形式表示的(集合之间绝不能相交,即图中任意两个圈不能相交)。

图 2(B)使用的是凹入表示法(了解即可),表示方式是:最长条为根结点,相同长度的表示在同一层次。例如 B、C、D 长度相同,都为 A 的子结点,E 和 F 长度相同,为 B 的子结点,K 和 L 长度相同,为 E 的子结点,依此类推。

最常用的表示方法是使用广义表的方式。图 1(A)用广义表表示为:
(A , ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )


普通树的存储结构

存储具有普通树的存储结构通常有三种方法

双亲表示法

孩子表示法

孩子兄弟表示法

双亲表示法

双亲表示法采用顺序表(数组)存储普通树

顺序存储各个节点的同时,给各节点附加一个记录其父节点位置的变量

因为根节点没有父节点,所以通常用-1来代替缺失的位置

孩子表示法

顺序表+链表

从树的根节点开始,使用顺序表依次存储树中各个节点

孩子表示法会给各个节点配备一个链表

用于存储各节点的孩子节点位于顺序表中的位置

如果这个节点没有孩子节点那么链表为空

孩子兄弟表示法

前面提到过同一层的节点互相称为兄弟节点

这里采用链表来存储

从树的根节点开始,依次用链表来存储各个节点的孩子节点和兄弟节点

所以链表中的节点中应该包含三部分的内容:

孩子指针域、数据域、兄弟指针域

通过孩子兄弟表示法,任意一棵普通树都可以相应转化为一棵二叉树

换句话说,任意一棵普通树都有唯一的一棵二叉树于其对应

所以孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法

通常又被称为”二叉树表示法”或”二叉链表表示法”

发表评论

您的电子邮箱地址不会被公开。