第六章 树和二叉树

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

1、第6章树和二叉树F6.1树的定义和基本术语F6.2二叉树F6.3遍历二叉树和线索二叉树F6.4树和森林F6.6赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）第6章树和二叉树1.树的定义注：树的定义具有递归性，即树中还有树。由一个或多个（n≥0）结点组成的有限集合。在任何一棵非空树T中：（1）有且仅有一个结点称为根（root）；（2）当n>1时，其余的结点分为m（m≥0）个互不相交的有限集合T1、T2…Tm。每个集合本身又是棵树，被称作这个根的子树。6.1树的定义和基本术语A只有根结点的树ABCDEFGHIJKLM根子

2、树6.1树的定义和基本术语树的抽象数据类型定义D是具有相同特性的数据元素的集合。ADTTree{}Tree数据对象D:数据操作P:数据关系R:若D是空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①Root唯一//关于根的说明②Dj∩Dk=//关于子树不相交的说明③…//关于数据元素的说明//至少15个6.1树的定义和基本术语图形表示法嵌套集合表示法广义表表示法凹入表示法（目录表示法）树的表示方法6.1树的定义和基本术语①图形表示法：…三亚学院理工分院人文分院管理分院通信测控电信计算机根子树ABCDE

3、FGH6.1树的定义和基本术语②广义表表示法：ABCDEFGH根作为由子树森林组成的表的名字写在表的左边A（B，C，D）A（B，C（E,F,G,H），D）③凹入表示法：ABCDEFGH6.1树的定义和基本术语ABCDEFGH④嵌套表示法：ABDCEGFH6.1树的定义和基本术语2.若干术语ABCDJEFGHIKLM根----根结点（没有前驱）森林----指m棵不相交的树的集合有序树----结点各子树从左至右有序，不能互换（左为第一）无序树----结点各子树可互换位置双亲----上层的那个结点（直接前驱）孩子----下层结点的子树的根（直接后继）兄弟

4、----同一双亲下的同一层结点（孩子之间互称兄弟）堂兄弟----双亲位于同一层的结点（但并非同一双亲）祖先----从根到该结点所经分支的所有结点子孙----该结点下层子树的任一结点6.1树的定义和基本术语ABCDJEFGHIKLM结点----树中的数据元素结点的度----结点拥有的子树的数目（有几个直接后继度就是几）结点的层次----从根到该结点的层数（根结点算第一层）叶子----度为0的点（终端结点）分支结点----度不为0的点（非终端结点）树的度----所有结点度中的最大值（Max{各结点的度}）树的深度----所有结点中最大的层数（Max{各

5、结点的层次}）（或高度）6.1树的定义和基本术语已知一棵树的集合为{,,,,,,,,,,,,}，请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点G的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？（10）以C为根的子树的深度是多少？课堂练习(一

6、)k1k2k3k4k7k5k6一、对照右图回答下列问题：1、这棵树的根结点？2、这棵树的叶子结点？3、结点k3的度？4、这棵树的度？5、这棵树的深度？6、结点k1的孩子结点？7、结点k3的双亲结点？8、以k3为根的子树的深度？二、已知树的集合为{,,,,,,,,}，分别用图形表示法、广义表表示法、嵌套表示法、凹入表示法画出这棵树。课堂练习(一)二叉树的结构最简单，规律性最强；可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性

7、质3.二叉树的存储结构6.2二叉树1、二叉树的定义①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。基本特征：基本形态：①②③④⑤Æ具有3个结点的二叉树可能有几种不同形态？普通树呢？6.2二叉树---定义2、二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i>0）。问：第i层上至少有个结点？性质2：深度为k的二叉树至多有2k-1个结点（k>0）。性质3：对于任何一棵二叉树，若度2的结点数有n2个，叶子结点数为n0，则n0=n2+1。6.2二叉树---性质证明性质3：∵二叉树中全部结点数n=n0+

8、n1+n2(叶子数+度1的结数+度为2的结点数)又∵二叉树中全部结点数n=B+1(总分支数+根结点)（除根结点外，每个结点