数据结构课件-第6章.pdf

数据结构与算法 Data Structure and Algorithm 第6章 树 目 录 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 ６. ５树和森林 6.6 哈夫曼树 6.1 树的基本概念 6.1.1 树的定义 1．树的定义 树是由n （n≥0 ）个结点组成的有限集合。若n=0，称为空树；若n0，则 ： （1）有一个特定的称为根 （root ）的结点。它只有直接后继，但没有直接前 驱； （2 ）除根结点以外的其它结点可以划分为m （m≥0 ）个互不相交的有限集合 T ，T ，…，T ，每个集合T （i=0,1,…,m-1）又是一棵树，称为根的子树 0 1 m-1 i ，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继 。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概 念。 树的结构参见图6-1。 A B D C E F G H I Ø A J K L M （a ）空树 （b ）仅含有根结点的树 （c ） 含有多个结点的树 图6-1 树的示意图 B C D G H I E F M J K L (a) T 子树 (b)T 子树 (c)T 子树 0 1 2 图6-2 图6-1(C)的树的三个子树 2 ．树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为： tree =(k,R) k={k ∣1≤i≤n;n≥0,k elemtype} i i 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 ，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 ．树的基本运算