《数据结构》课程教学课件（讲稿，C语言描述）第6章 树

树第6章数据结构（C语言描述

第6章 树 数据结构（C语言描述）

目录6.1树的基本概念6.2二叉树6.3遍历二叉树6.4线索二叉树6.5树和森林哈夫曼树6.6退出

6.6 哈夫曼树 6.5 树和森林 6.4 线索二叉树 6.3 遍历二叉树 6.2 二叉树 6.1 树的基本概念 退 出 目 录

6.1树的基本概念6.1.1树的定义1．树的定义树是由n（n>0）个结点组成的有限集合。若n=0，称为空树：若n>0，则：(1)有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；(2)除根结点以外的其它结点可以划分为m（m>0）个互不相交的有限集合T。，T，…，T㎡l，每个集合T（i=0,1,...,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图6-1

6.1 树的基本概念 6.1.1 树的定义 1．树的定义 树是由n（n≥0）个结点组成的有限集合。若n=0，称为空 树；若n>0，则： （1）有一个特定的称为根（root）的结点。它只有直接 后继，但没有直接前驱； （2）除根结点以外的其它结点可以划分为m（m≥0）个 互不相交的有限集合T0，T1，.，Tm-1，每个集合Ti （i=0,1,.,m-1）又是一棵树，称为根的子树，每棵子树 的根结点有且仅有一个直接前驱，但可以有0个或多个直 接后继。 由此可知，树的定义是一个递归的定义，即树的定义中 又用到了树的概念。 树的结构参见图6-1

0M(a）空树（b）仅含有根结点的树(c）含有多个结点的树图6-1树的示意图

A A B C D E F G H I J K L M （a）空树 （b）仅含有根结点的树 （c） 含有多个结点的树 图 6-1 树的示意图 Ø

在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T，T，T2，具体请参见图6-2，其中T=(B,E, F,J,K,L),T=(C,G), T,=(D,H,I，M)，其中的T。，T，T,都是树，称为图6-1（C)中树的子树，而T，T，T,又可以分解成若干棵不相交子树。如T可以分解成To，To,两个不相交子集，Too={E，J，K，L)，Tor={F}，而To又可以分为三个不相交子集Tooo，Too1，To02，其中，Tooo={J),Too1={K),To02={L)。M(a)T。子树(b)T子树(c)Tz子树图6-2图6-1(C)的树的三个子树

在图6-1(c)中，树的根结点为A，该树还可以分为三个 互不相交子集T0，T1，T2，具体请参见图6-2，其中 T0 ={B，E，F，J，K，L}，T1 ={C，G}，T2 ={D，H， I，M}，其中的T0，T1，T2都是树，称为图6-1（C） 中树的子树，而T0，T1，T2又可以分解成若干棵不相 交子树。如T0可以分解成T00，T01两个不相交子集， T00={E，J，K，L}，T01={F}，而T00又可以分为三个 不相交子集T000，T001，T002，其中，T000={J}， T001={K}，T002={L}。 C G B E F J K L D H I M (a) T0子树 (b)T1子树 (c)T2子树 图 6-2 图 6-1(C)的树的三个子树

2.树的逻辑结构描述一棵树的逻辑结构可以用二元组描述为：tree =(k,R)k={k, 1 10,k,eelemtype)R=(r)其中，n为树中结点个数，若 n=0，则为一棵空树，n>0时称为一棵非空树，而关系r应满足下列条件：有且仅有一个结点没有前驱称该结点为树根：(2除根结点以外，其余每个结点有且仅有一个直接前驱;(3)树中每个结点可以有多个直接后继（孩子结点）

2．树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为： tree =(k,R) k={ki∣1≤i≤n;n≥0,kielemtype} R={r} 其中，n为树中结点个数，若 n=0，则为一棵空树， n> 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前 驱; （3）树中每个结点可以有多个直接后继(孩子结点)

例如，对图6-1(c）的树结构,可以二元组表示为K=IA, B, C, D,E, F, G,H,I, J,K,L, M?R=(r)r=((A,B),(A,C)，(A,D)，(B,E)，(B,F)，(C,G),(D,H)，(D,I),(E,J),(E,K)，(E,L),(H,M))3.树的基本运算树的基本运算可以定义如下几种：①inittree(&T)初始化树T。(2)root(T)求树T的根结点

例如，对图6-1(c )的树结构,可以二元组表示为： K={A，B，C，D，E，F，G，H，I，J，K，L，M} R={r} r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)， (D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)} 3．树的基本运算 树的基本运算可以定义如下几种： (1) inittree(&T) 初始化树T。 (2) root(T) 求树T的根结点

(3)parent(T,x)求树T中，值为x的结点的双亲。(4)child(T,x,i)求树T中，值为x的结点的第i个孩子。(Saddchild(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6)delchild(x,i)删除值为x的结点的第i个孩子。(7)traverse(T)遍历或访问树T

(3) parent(T,x) 求树T中，值为x的结点的双亲。 (4) child(T,x,i) 求树T中，值为x的结点的第i个孩子。 (5) addchild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树 中。 (6) delchild(x,i) 删除值为x的结点的第i个孩子。 (7) traverse(T) 遍历或访问树T

6.1.2基本术语1.结点指树中的一个数据元素，一般用一个字母表示。2.度一个结点包含子树的数目，称为该结点的度。3.树叶（叶子）度为0的结点，称为叶子结点或树叶，也叫终端结点。4.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B, C, D

6.1.2 基本术语 1.结点 指树中的一个数据元素，一般用一个字母表示。 2.度 一个结点包含子树的数目，称为该结点的度。 3.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结 点。 4.孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也 称为孩子，儿子，子女等。如图6-1（c）中A的孩子为 B，C，D

5.双亲结点若结点X有子女Y，则X为Y的双亲结点。6.祖先结点从根结点到该结点所经过分支上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。7.子孙结点某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点具有同一个双亲的结点，称为兄弟结点

5.双亲结点 若结点X有子女Y，则X为Y的双亲结点。 6.祖先结点 从根结点到该结点所经过分支上的所有结点为该结点的 祖先，如图6-1（c）中M的祖先有A，D ，H 。 7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。 8.兄弟结点 具有同一个双亲的结点，称为兄弟结点