非线性结构复习要点.pptVIP

复习课 主讲人：陈红丽 第六章 树 本章是重点章，二叉树又是本章的重点内容，我们要了解树的定义，熟悉二叉树的定义、性质、存储结构、遍历、线索化和树的存储结构、遍历以及树、森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。算法的重点是二叉树的遍历及其有关应用。 树的概念：树(Tree)是n(n=0)个结点的有限集T。T为空时称为空树，否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。 树的逻辑结构特征是：非空树存在唯一一个根结点（没有前驱）。树中任一结点都可以有零个或多个直接后继(孩子)结点，但至多只能有一个直接前趋(双亲)结点。树形结构是非线性结构。有序树中兄弟结点之间从左至右有次序之分。 树的四种不同表示方法中掌握树形表示法(注意树枝无方向箭头)。 二叉树： 二叉树的定义：二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树的五种基本形态。 满二叉树----深度为 k ，且有 2k-1 个结点的二叉树； 完全二叉树----结点数2k-1-1n≤2k-1 二叉树的重要性质： 二叉树第i层上的结点数目最多为2i-1(i≥1) 深度为k的二叉树至多有2k-1个结点(k≥1)。 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。 具有n个结点的二叉链表有（n+1）个空指针域。 具有n个结点的完全二叉树的深度为|_lgn_|+1 (或|﹉lg(n+1)﹉|）。 具有n个结点的完全二叉树，叶子结点有（ |﹉n/2﹉|)个，度为1的结点有（0或1）个。 如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点 i (1≤i≤n)，有： 1、如果 i=1，则结点 i是二叉树的根，无双亲；如果 i 1，则其双亲是结点 ?i/2?。 2、如果 2i n，则结点 i无左孩子，为叶结点；否则其左孩子是结点 2i。 3、如果 2i+1 n，则结点 i无右孩子；否则其右孩子是结点 2i+1。 二叉树的顺序存储结构就是把二叉树的所有结点按照层序(从根结点起，从上到下，从左往右编号)存储到一片连续的存储单元中 。 对于顺序存储方式的二叉树，可以根据结点的编号直接得出结点之间的逻辑关系（性质5），这里应该会计算(应用)，比如知道一个结点的序号，要我们计算其双亲的序号，兄弟、孩子等序号。 二叉树的链式存储－－二叉链表法。结点的结构为两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据。该二叉树由根指针root唯一确定。 三、二叉树的遍历： 根据访问结点的次序不同可得三种遍历：先序遍历(前序遍历或先根遍历)，中序遍历(或中根遍历)、后序遍历(或后根遍历)。 对于一给定的二叉树，根据不同的遍历方法，应能得出其相应的结点访问次序。只要将有哪些信誉好的足球投注网站路线上所有在第一次、第二次、第三次经过的结点分别列表就可得到该二叉树的先序序列、中序序列和后序序列。 根据遍历序列画出二叉树。 已知一棵二叉树的先序序列和中序序列，构造该二叉树的过程如下： 1. 根据先序序列的第一个元素建立根结点； 2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列； 3. 在先序序列中确定左右子树的先序序列； 4. 由左子树的先序序列和中序序列建立左子树； 5. 由右子树的先序序列和中序序列建立右子树。 已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下： 1. 根据后序序列的最后一个元素建立根结点； 2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列； 3. 在后序序列中确定左右子树的后序序列； 4. 由左子树的后序序列和中序序列建立左子树； 5. 由右子树的后序序列和中序序列建立右子树。 四、线索二叉树： 利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为线索，加上线索的二叉链表就称为线索链表。 五、树和森林： 树和森林及二叉树的转换：三者是唯一对应的，它们之间的转换办法应掌握。 树变二叉：兄弟相连留长子。 林变二叉：树变二叉根相连。 二叉变树：左孩右右连双亲，去掉原来右孩线。 树的遍历 树的先序遍历 对应二叉树的先序遍历； 树的后序遍历 对应二叉树的中序遍历。 六、哈夫曼树及其应用 树的路径长度是从树根到树中每一结点的