树第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)的树的三个子树