第6章树 数据结构(C++描述)
第6章 树 数据结构（C++描述）
目录 61树的基本概念 62二叉树 63遍历二叉树 64线索二叉树 6.5树和森林 66哈夫曼树 退出
6.6 哈夫曼树 ６.５树和森林 6.4线索二叉树 6.3遍历二叉树 6.2 二叉树 6.1 树的基本概念 退出 目录
61树的基本概念 611树的定义 1.树的定义 树是由n(n≥0)个结点组成的有限集合。若n=0,称为空 树;若n>0,则: (1有一个特定的称为根(oo)的结点。它只有直接 入后继,但没有直接前驱 (2)除根结点以外的其它结点可以划分为m(m0)个 互不相交的有限集合T,T1,…,Tm1,每个集合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
(a)空树(b)仅含有根结点的树(c)含有多个结点的树 图6-1树的示意图
A A B C D E F G H I J K L M （a）空树 （b）仅含有根结点的树 （c） 含有多个结点的树 图 6-1 树的示意图 Ø
g?在图61()中,树的根结点为A,该树还可以分为三个 互不相交子集T,T1,T2,具体请参见图6-2,其中 To-B,E, F, J, K, L, T(C,G), T=D,H, 1,M,其中的rn,T,T2都是树,称为图61(C 中树的子树,而T,T1,T2又可以分解成若干棵不相 交子树。如T可以分解成To,T1两个不相交子集, T0={E,J,K,L},To1={F},而To可以分为三个 不相交子集T00T0,T02,其中,To={J}, 001 K},To02={L}。 (a)To子树 (b)T1子树(c)T2子树 图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)的树的三个子树