资源描述：
《数据结构-第六章 树和二叉树.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、基本内容二叉树的概念、性质和存储结构；二叉树的遍历和线索化算法；树的定义、存储结构、树与二叉树的转换、树的遍历；哈夫曼树的构造；学习要点1．掌握二叉树的结构特性；2．熟悉二叉树的各种存储结构的特点及适用范围；3．遍历二叉树是二叉树各种操作的基础。掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作；4．理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5．熟悉树的各种存储结构及其特点，掌握树与二叉树的转换方法，掌握树的遍历
2、方法；6．了解哈夫曼树的特性，掌握构造哈夫曼树和哈夫曼编码的方法。第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4树和森林6.5树与等价问题*6.6哈夫曼树及应用6.1树的有关概念1.树的概念2.树的应用3.树的表示4.树的有关术语5树的基本操作6.1树的定义和基本术语1．树的概念树结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有零个或多个直接后继。树是n个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为m个互不相交的集合，而且这些集合中的每一集合本身又是一
3、棵树，称为根的子树。ABCDEFGHIJ树是递归结构，在树的定义中又用到了树的概念例：下面的图是一棵树ABCDEFGHIJT={A,B,C,D,E,F,G,H,I,J}A是根，其余结点可以划分为3个互不相交的集合：T1={B,E,F},T2={C,D},T3={D,H,I,J}这些集合中的每一集合都本身又是一棵树，它们是A的子树。例如对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E}，T12={F}，T11,T12是B的子树。ABCDEFGHIJ从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且
4、仅有一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一一条从根到该结点的路径；5）树是一种分支结构2．树的应用1）树可表示具有分支结构关系的对象例1．家族族谱设某家庭有10个成员A、B、C、D、E、F、G、H、I、J，他们之间的关系可下图所示的树表示：ABCDEFGHIJ例2．单位行政机构的组织关系2）树是常用的数据组织形式有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统不论是DOS文件系统还是window文件系统，所有的文件是用树的形式
5、来组织的。C文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件123）问题的求解过程可用树结构的来描述一些应用问题的求解过程可用树结构的来描述，以帮助程序员写出求解问题的程序或算法。例4求集合的幂集求集合A={1，2，3}的幂集集合中每个元素对于子集来说，要么属于该子集，要么不属于该子集考虑元素1{}例如1不属于{2，3}，左面的考虑元素2{1}{}树从空集开始，考虑元素3{1,2}{1}{2}{}构造集合的子集{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}显然集合A的所有子集即为该树的所有叶子结点，求
6、集合A的幂集即为求该树的所有叶子。3树的表示1）图示表示2）二元组表示3）文氏图表示4）凹人表示法（类似书的目录）5）广义表表示4.树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的高度：树中最大的结点层结点的度：结点子树的个数树的度：树中最大的结点度。叶子结点：也叫终端结点，是度为0的结点；分支结点：度不为0
7、的结点；森林:互不相交的树集合；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；叶子：K，L，F，G，M，I，J结点A、D的度：3度为0结点B、E的度：2树的度：3结点C、H的度：1结点I的双亲：DA结点L的双亲：E结点A为树的根结点A的孩子：B，C，D结点B，C，D为兄弟BCD结点B的孩子：E，F结点K，L为兄弟EFGHIJKLM结点F，G为堂兄弟结点A的层次：1结点A是结点F，G的祖先结点M的层次：4树的深度：45树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）InitTree(&T
8、);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);8）Value(T,&cu
