第六章树和二叉树.ppt

《第六章树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树6.1树的结构定义和基本操作6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5树与等价问题6.6哈夫曼树及其应用6.7回溯法与树的遍历6.8树的计数16.1树的定义和基本概念一、树的定义：树是n(n>=0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个特定的称为根的结点。(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树。例：A(a)只有一个结点的树2(b)GBDCEFIHMJKAL13个结点的树：（1）A为根结点；（2

2、）T1，T2，T3三个子树；T1={B，E，K，L，F}T2={C，G}T3={D，H，M，I，J}树的其它表示形式：（1）是以广义表的形式表示的。（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）））3（2）以嵌套集合的形式表示。KLEFBMHIJDGCA（3）用凹入表示法。ABEKLFCGDHMIJ4二、树的基本概念：结点——包含一个数据元素及若干指向其子树的分支。结点的度——结点拥有的子树数。叶子（或终端结点）——度为0的结点。非终端结点（或分支结点）——度不为0的结点。5树的度——是树内各结点的度的最大值。结点的孩

3、子——该结点的子树的根；相应地，该结点称为孩子的双亲。GBDCEFIHMJKAL同一个双亲的孩子之间互称兄弟。兄弟——是从根到该结点所经分支上的所有结点。结点的祖先——以该结点为根的子树中的任一结点。结点的子孙——6GBDCEFIHMJKAL从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次。结点的层次——堂兄弟——其双亲在同一层的结点互为堂兄弟。树的深度（或高度）——如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树。否则称为无序树。有序树——7森林——是m(m>=0)棵互不相交的树的集合。8抽象数据类型树

4、的定义：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H},H是如下的二元关系：(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Φ,则存在D-{root}的一个划分D1,D2,…,Dm(m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且对任意的i（1≤i≤m),惟一存在数据元素xi∈Di,有∈H;9抽象数据类型树的定义：(3)对应于D-{root}的划分，H-{

5、ot,x1>,…}有惟一的一个划分H1，H2,…,Hm(m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ，且对任意的i（1≤i≤m),，Hi是Di上的二元关系，(Di,{Hi})是一颗符合本定义的树，称为根root的子树。基本操作：｝ADTTree10整个树可以用二元组(D,{H})表示。其中：D={{root},D1,D2,…,Dm}H={,,…,,H1,H2,…,Hm}(root代表树的根)第i棵子树用二元组(Di,{Hi})表示。其中：该子树的根为X

6、i∈Di。上述关于树的定义是一种递归定义：树由m+1个基本单元组成：1个根结点和m个子树。11（1）InitTree(&T);操作结果：构造空树T（2）DestroyTree(&T);初始条件：树T存在操作结果：销毁树T12（3）CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。（4）ClearTree(&T);初始条件：树T存在。操作结果：将树T清为空树。13（5）TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRU

7、E；否则返回FALSE。（6）TreeDepth(T);初始条件：树T存在。操作结果：返回T的深度。（7）Root(T);初始条件：树T存在。操作结果：返回T的根。14（8）Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。（9）Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。15（10）Parent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根

8、结点，则返回它的双亲，否则函数值为“空”（11）LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。16（12）