数据结构_第6章 树和二叉树

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

1、第6章树和二叉树学习要点理解树的定义和基本术语，重点了解二叉树的定义、性质和存储结构。掌握二叉树遍历的递归算法及它的典型运算。理解线索化二叉树的特性以及寻找某结点的前驱和后继的方法。理解树、森林和二叉树间的相互转换规则。掌握哈夫曼树的实现方法，理解构造哈夫曼编码及带权路径长度的计算。6.1树的基本概念什么是树？树是由n(n≥0)个结点的有限集合。如果n=0，称为空树；如果n>0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1，除根以外的其它结点划分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵

2、树，并且称为根的子树(SubTree)。注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。T={A，B，C，D，E，F，G，H，I，J，K，L}A是根，其余结点可以划分为3个互不相交的集合：T1={B，E，F，K，L}T2={C，G}T3={D，H，I，J，M}这些集合中的每一集合都本身又是一棵树，它们是A的子树。对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E，K，L}T12={F}T11，T12是B的子树。HBAJFEDKLCMIG树的示例1.树中只有根结点没有前驱

3、；2.除根外，其余结点都有且仅一个前驱；3.树的结点，可以有零个或多个后继；4.除根外的其它结点，都存在唯一条从根到该结点的路径；5.树是一种分支结构(除了一个称为根的结点外)每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。HBAJFEDKLCMIG树的逻辑结构特点树可表示具有分支结构关系的对象例1.家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。例2.单位行政机构的组织关系HBAJFEDKLCMIG树的应用树是常用的数据组织形式有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理

4、和使用数据，将它们用树的形式来组织。例3.计算机的文件系统不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹2文件1文件2文件夹11文件夹11文件11文件12C树的应用树的结点：包含一个数据元素的内容及若干指向子树的分支。孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如B是E的双亲。兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；如H的祖先

5、为A、D。子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIG6.1.3基本术语结点的度：结点子树的个数；如D的度为3。叶子结点：也叫终端结点，是度为0的结点；如K、L、F、G、M、I、J。分支结点：度不为0的结点；如A、B、C、D结点层次：根结点的层定义为1，根的孩子为第二层结点，依此类推。树的高度：树中结点的最大层次；如图所示树的高度为4。树的度：树中各结点的度的最大值；如图所示树的度为3。森林：m(m>=0)棵互不相交的树的集合；HBAJFEDKLCMIG基本术语1.双

6、亲表示法：以一组连续的空间存储树的结点，通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。其类型定义如下：#defineMAX_TREEE_SIZE100typedefstructPTNode{ElemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}Ptree;特点：找双亲容易，找孩子难ARDCFEGBHKA0B0C0D1E1F3G6H6R-1K60123456789数组下标6.2树的存储结构通过保存每个结点的孩子结点的位置，表示树

7、中结点之间的结构关系。多重链表：每个结点有多个指针域，分别指向其子树的根。结点同构：结点的指针个数相等，为树的度d。结点不同构：结点指针个数不等，为该结点的度d。6.2.2孩子表示法孩子链表：其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。孩子表示法ARDCFEGBHKAB^CD^E^