树与二叉树学习导读

《树与二叉树学习导读》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树与二叉树学习导读树型结构（Tree）是一类重要的非线性数据结构。其中以树和二叉树最为常见，树是以分支关系定义的层次结构。人类社会的族谱和各种社会组织机构都可用树来形象表示。编译程序中，可用树来表示源程序的语法结构。数据库系统中，树型结构也是信息的重要组织形式之一。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树的转换关系，最后介绍一个典型的应用例子：哈夫曼树和哈夫曼编码。1.树的定义和基本术语2.二叉树3.遍历二叉树和线索二叉树4.树与森林5.赫夫曼树及其应用6.1树的定义和基本术语1、树(Tre

2、e)的定义树是n（n≥0）个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特殊的称为根(Root)的结点；（2）当n＞1时，其余结点可分成m（m＞0）个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。如图6.1：A为根结点;（B，E，F）、（C，G，H，J，K，L，M）、（D，I）分别为根结点A的三棵子树。B，C，D分别为三棵子树的根结点。显然这是一个递归定义。图6.1树的示意图ABCDEFGHIJKLMRootABCDEFGHIJKLMRoot上述树的定义加

3、上树的一组基本操作构成抽象数据类型树的定义:ADTTree{数据对象D:D是具有相同特性的数据对象的集合。数据关系R:若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：⑴在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；⑵若D-{root}≠Φ，则存在D-{root}的一个划分D1，D2，…，Dm（m＞0），对任意j≠k（1≤j，k≤m）有Dj∩Dk=Φ，且对任意的i（1≤i≤m），唯一存在数据元素xi∈Di，有＜root，xi＞∈H；⑶对应于D-{root}的划分，

4、H-{＜root，x1＞，…，＜root，xm＞}有唯一的一个划分H1，H2，…，Hm（m＞0），对任意j≠k（1≤j，k≤m）有Hj∩Hk=Φ，且对任意的i（1≤i≤m），Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。基本操作P：15个。P119}ADTTreeABCDEFGHIJKLMRoot(A(B(E,F(I,J)),C,D(G,H)))第一层第二层第三层第四层高度=4ABCDEGHIFJJIHGFEDCBAABEFIJCDGHE广义表表示法树形表示法嵌套集合表示法凹入表表

5、示法树的各种表示法IJ2、树中结点的度(Degree)与树的度树中每个结点的分枝数称为该结点的度。例如图6.1中根结点A的度为3。B的度为2。G的度为4。而E，F，H，I，J，K，L，M的度全为零。树的度是树中结点的最大度数。所以图6.1的度为4。在实际应用中我们称度为零的结点为叶子(Leaf)结点，称度不为零的结点为分枝结点。如图6.1中E，F，H，I，J，K，L，M都是叶子结点，B，C，D，G都是分枝结点。从树中我们知道度为4的树中结点的度有0，1，2，3，4五种。因而可推知度为m的树中结点的度有m+1种。ABCDE

6、FGHIJKLMRoot3、孩子(Child)结点与双亲(Parent)结点树中结点的子树的根结点称为该结点的孩子结点。相反，称该结点为孩子结点的双亲。例如图6.1中，B，C，D是根结点A的三个孩子结点。A为B，C，D的双亲。而，B，C，D三个结点又互称为兄弟(Sibling)结点（它们具有同一个双亲）。而E，F，G，H，I称为堂兄弟（它们的双亲称为兄弟结点）。祖先结点是从根结点到达某结点所经过分枝上的所有结点通称为该结点的祖先。例如A，C，G为结点J，K，L，M的祖先。子孙结点以某结点为根的子树中的任一结点都称为该结点

7、的子孙。例如G，H，J，K，L，M都是C的子孙。ABCDEFGHIJKLM图6.1树的示意图ABCDJKLM4、树中结点的层数(Level)从根结点开始，根为一层结点，其孩子结点为二层结点依次类推，叶子结点为最下层结点。例如:右图示。这种分层的好处是树中结点的最大层数称为该树的高度（深度）。所以右图（用黑数字）所示树的高度（深度）为4。实际应用中树也可以以根为0层结点开始，此时，结点的层数为从根到达该结点的路径长度。如果，知道树中每层结点的个数，便可计算出对树中所有结点查找一遍所花费的总代价。使用哪种方式用户可根据系统需

8、要进行选择。0……………………..11…………22…E.FGHI…33…….….4Root5、森林（Forest)是m(m>=0)棵互不相交的树的集合（可以看成是把一棵树的根结点去掉，所得到的子树构成森林）。例如图6.2为图6.1去掉根结点A，以其三个孩子结点B，C，D为根的三棵子树构成的森林。6、有序树与无序树如果