第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)的树的三个子树
2.树的逻辑结构描述 棵树的逻辑结构可以用二元组描述为 tree=(k,R) k={k;|1sinn≥0.k;∈ elemtype R={r} 其中,n为树中结点个数,若n=0,则为一棵空树,n> 0时称为一棵非空树,而关系r应满足下列条件 (1)有且仅有一个结点没有前驱称该结点为树根 (2除根结点以外其余每个结点有且仅有一个直接前 驱: 3)树中每个结点可以有多个直接后继(孩子结点)
2．树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为： tree =(k,R) k={ki∣1≤i≤n;n≥0,kielemtype} R={r} 其中，n为树中结点个数，若 n=0，则为一棵空树， n> 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前 驱; （3）树中每个结点可以有多个直接后继(孩子结点)
:例如,对图6-1(c)的树结构可以二元组表示为 K-A,B, C, D,E, F, G, H, I,J,K, L, Mi R={r} r={(A,B),(A,C),(A,D),(B,E),(B,F),(CG), (D,H),(D,I),(E,J),(E,K),(E,L),(HM) 3.树的基本运算 树的基本运算可以定义如下几种: (intree(&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个孩子。 (5)addchild(y,i, x) 把值为x的结点作为值为y的结点的第个孩子插入到树 (6)delchild(x, i) 删除值为x的结点的第i个孩子 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
612基本术语 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.兄弟结点 具有同一个双亲的结点，称为兄弟结点