大话数据结构-第6章 树 149- 高飞网

第6章 树 149

2016-12-22 18:14:20.0

6.2 树的定义

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(root)的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(subTree)。


    对于树的定义还需要强调两点:

  1. n>0时根结点是唯一的,不可能存储多个根结点。
  2. m>0时,子树的个数没有限制,但它们一定是互不相交的。下图中的两个结构就不符合树的定义,因为它们都有相交的子树。

6.2.1 结点分类

    结点拥有的子树称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点度的最大值。



6.2.2 结点间关系

    结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。


6.2.3 树的其他相关概念

    结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为兄弟。树中结点的最大层次称为树的深度(Depth)或高度。


    如果将树中的结点的各个子树看成从左到右是有次序的,不能互换的,则称该树为有序树,否则称为无序树。

    森林(Forest)是m(m>=0)棵互不相交的树的集合。

6.3 树的抽象数据类型

ADT 树(tree)
Data
	树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系
Operation
	InitTree(*T):构造空树T
	DestroyTree(*T):销毁树T
	CreateTree(*T,definition):按definition中给出树的定义来构造树
	ClearTree(*T):若树T存在,则将树T清为空树
	TreeEmpty(T):若T为空树,返回true,否则返回false
	TreeDepth(T):返回T的深度
	Root(T):返回T的根结点
	Value(T,cur_e):cur_e是树T中的一个结点,返回此结点的值 
	Assign(T,cur_e,valule):给树T的结点cur_e赋值为value
	Parent(T,cur_e):若cur_e是树T的非根结点,则返回它的双亲,否则返回空
	LeftChild(T,cur_e):若cur_e是树T的非叶子结点,则返回它的最左孩子,否则返回空
	RightSibling(T,cur_e):若cur_e有右兄弟,则返回它的右兄弟,否则返回空
	InsertChild(*T,*p,i,c):其中p指向树T的某个结点,i为所指结点p的度上加1,非空树c与T不相交,操作结果为插入c为树T中p结点的第i棵子树
	DeleteChild(*T,*p,i):其中p指向树T的某个结点,i为所指结点p的度,操作结果为删除T中p所指结点的第i棵子树。
endADT

6.4 树的存储结构

6.4.1 双亲表示法

       除了根结点外,每个结点都有一个双亲结点,因此,假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置

/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType; /* 树结点的数据类型,目前暂定为整型 */
typedef struct PTNode /*结点结构*/
{
	TElemType data;/*结点数据*/
	int parent;/* 双亲位置 */
}PTNode;
typedef struct
{
	PTNode nodes[MAX_TREE_SIZE];/* 结点数据 */
	int r,n;/* 根的位置和结点数 */
}PTree;

    双亲表示法,知道一个结点的情况下,获取双亲结点,可以通过到双亲的结点指针直接得到,时间复杂度为O(1),但是如果想得到其孩子结点,却必须遍历整个树,时间复杂度为O(n)。这时可以再在结点上添加指向孩子的结点。

6.4.2 孩子表示法

    由于树中每个结点可能有多棵子树,可以考虑用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法

    方案一:一种是指针域的个数就等于树的度(树各个结点度的最大值)。

    这种方法对于树中各结点的度相差很大时,显示很浪费空间的。因为有很多的结点,它的指针域都是空的。不过如果树的各结点度相差很小雨时,那就意味着开辟的空间被充分利用了,这时存储结构的缺点反而变成了优点。

    方案二:第二种方案每个结点指针域的个数等于该结点的度。

    这种方法克服了浪费空间的缺点,对空间利用率是很高了,但是由于各个结点的链表是不相同的结构,加上要维护结点的度的数值,在运算上就会带来时间上的损耗

    能否有更好的方法,既可以减少空指针的浪费又能使结点结构相同

    我们要遍历整棵树,把每个结点放到一个顺序存储结构的数组中是合理的,但每个结点的孩子多少是不确定的,所以我们再对每个结点的孩子建立一个单链表体现它们的关系。

    这就是我们要讲的孩子表示法。把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链个为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存储一个一维数组中。

/* 树的孩子表示法结构定义  */
#define MAX_TREE_SIZE 100
typedef struct CTNode /* 孩子结点 */
{
	int child;
	struct CTNode *next;
}*ChildPtr;
typedef struct
{
	TElemType data;
	ChildPtr firstchild;
}CTBox;
typedef struct/*树结构 */
{
	CTBox nodes[MAX_TREE_SIZE];/* 结点数组 */
	int r,n;/* 根的位置和结点数 */
}CTree;

    该结构的优点在于,查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。对于遍历整棵树也很方便,对头结点的数组循环即可。

    但也存在问题,如何知道某个结点的双亲是谁呢?目前只能遍历整个树,但也可以在数组中加一个parent的指针域,如下:


    这种方法称为双亲孩子表示法,应该算是孩子表示法的改进。

6.4.3 孩子兄弟表示法

    任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
	TElemType data;
	struct CSNode *firstchild,*rightchild;
}CSNode,*CSTree;


    该结构的优点,也是可以方便地找到某个结点的孩子,缺点也是找父结点需要遍历树,解决方法与上面的孩子表示法一样。

    该结构的最大好处,在于它把一棵复杂的树变成了一棵二叉树。