资源描述：
《数据结构 第6 章 树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、树和二叉树1、树和森林的概念（树的定义、树的术语、性质及运算）；2、二叉树的定义、性质及运算；3、二叉树的存储结构（顺序、链式表示）；4、遍历二叉树5、树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林6、哈夫曼树、哈夫曼编码。教学内容树型结构（非线性结构）结点之间有分支具有层次关系例自然界：树人类社会家谱行政组织机构计算机领域编译：用树表示源程序的语法结构数据库系统：用树组织信息算法分析：用树描述执行过程国务院山东省北京市西藏自治区…济南市青岛市威海市…历下区市中区…商河县6.1树的定义和基本术语定义：树(Tree)是n(n≥0)个结点的有限集。若n=0，
2、称为空树；若n>0，则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。显然，树的定义是一个递归的定义。树的逻辑结构：树中任一结点都可以有零个或多个直接后继结点但至多只能有一个直接前趋结点。T3T2T1基本术语：结点的度：结点拥有的子树数。度=0叶子终端结点度≠0分支结点非终端结点根结点以外的分支结点称为内部结点树的度：树内各结点的度的最大值。双亲孩子兄弟结点的祖先：从根到该结点所经分支上的所有结点。结
3、点的子孙：以某结点为根的子树中的任一结点。第1层第2层第3层第4层堂兄弟双亲在同一层的结点树的深度：树中结点的最大层次。有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。无序树：树中结点的各子树无次序。结点：数据元素+指向子树的分支根结点：非空树中无前驱结点的结点森林：是m(m≥0)棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。把根结点删除树就变成了森林。给森林中的各子树加上一个双亲结点，森林就变成了树。树森林一定是不一定是EFGHIABCDJKLM树的逻辑结构描述一棵树的逻辑结构可以用二元组描述为：Tree=(root,F)数据元素根结点
4、包含m(m≥0)棵树的森林F=(T1,T2,…,Tm)Ti=(ri,Fi)Ti称做根root的第i棵子树。当m≠0时，在树根和其子树森林之间存在下列关系：RF={
5、i=1,2,…,m,m>0}RF={,,}Tree=(A,F)F=(T1,T2,T3)T1=(B,F1)T2=(C,F2)T3=(D,F3)……r1F1={,}r2F2={}r3F3={,,}……EFGHIABCDJKLM树的抽象数据类型定义：ADTTree{数据对象D：D是具有相同特性的数据元
6、素的集合。数据关系R：（略）基本操作P：{结构初始化}InitTree(&T)；操作结果：构造空树T。CreateTree(&T,definition)；初始条件：definition给出树T的定义。操作结果：按definition构造树T。{销毁结构}DestroyTree(&T)；初始条件：树T存在。操作结果：销毁树T。{引用型操作}TreeEmpty(T)初始条件：树T存在。操作结果：若T为空树，则返回TURE，否则FALSE。TreeDepth(T)初始条件：树T存在。操作结果：返回T的深度。Root(T)初始条件：树T存在。操作结果：返回T的根。Val
7、ue(T,cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Assign(T,cur_e,value)初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。Parent(T,cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T,
8、cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。TraverseTree(T,Visit())；初始条件：树T存在，Visit是对结点操作的函数。操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败。{加工型操作}ClearTree(&T)；初始条件：树T存在。操作结果：将树T清为空树。InsertChild(&T,&p,i,c)；初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度+1，非空树c与T不相交。操作结果：插
9、入c为T中p指结点的第i
