数据结构第6章1VIP免费

课前导学6.1树的定义和基本术语6.2二叉树6.3遍历二叉树6.4树和森林6.5赫夫曼树及其应用【学习目标】1．领会树和二叉树的类型定义。2．熟记二叉树的主要特性，并掌握它们的证明方法。3．熟练掌握二叉树的各种遍历算法。4．熟练掌握二叉树和树的各种存储结构及其建立的算法。5．熟练掌握二叉树和树的各种存储结构及其建立的算法。6．了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。【重点和难点】重点：二叉树和树的遍历及其应用难点：编写实现二叉树和树的各种操作的递归算法【知识点】树、二叉树、二叉树的遍历、树和森林的存储表示、树和森林的遍历、最优树和哈夫曼编码【课前思考】你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。上列家族谱系图可用如下关系表示：<祖父，伯父>，<祖父，父亲>，<祖父，叔父>，<伯父，堂兄>，<伯父，堂姐>，<父亲，你>，<叔父，堂弟>，<堂兄，侄儿>以上就是本章讨论的对象:树型数据结构6.16.1树的定义和基本术语树的定义和基本术语定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先树的抽象数据类型:ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作P：InitTree(&T);操作结果：构造空树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回T的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Parent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则返回"空"。LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回"空"。TraverseTree(T,visit());初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。ClearTree(&T);初始条件：树T存在。操作结果：将树T清为空树。InsertChild(&T,&p,i,c);初始条件：树T存在，p指向...