数据结构章树和叉树.pptVIP

* 数据结构 * 例7.1 含n个结点的三次树的最小高度是多少？最大高度是多少？ 解：设含n个结点的(为完全三次树时高度最小)的三次树的最小高度为h,则有： 1+3+9+…+3h-2＜n≤1+3+9+…+3h-1 (3h-1-1)/2 ＜n≤ (3h-1)/2 3h-1＜2n+1≤3h 即：h= ? log3(2n+1)? 最大高度为n-2。 * 数据结构 * 若一棵三次树中度为3的节点为2个，度为2的节点为1个，度为1的节点为2个，则该三次树中总的节点个数和度为0的节点个数分别为多少？ 总节点个数n=11 度为0的节点（叶子节点）个数n0=6 * 数据结构 * 本 章 小 结 1、定义和性质 2、存储结构 3、遍历 4、线索化 顺序结构 链式结构 二叉链表 三叉链表 先序线索树 中序线索树 后序线索树 树 二叉树 森林 Huffman编码 1:2， 性质有3+2条 先 序 遍 历 中 序 遍 历 遍历 存储结构 遍历 孩子—兄弟 先序遍历 后序遍历 线索树 Huffman树 应用 中序遍历 后序遍历 先序遍历 层次遍历 第6章结束 * 数据结构 * 作业 1如果一棵树有n1个度为1的结点，有n2 个度为2的结点，有n3个度为3的结点，则该树有多少个度为0 的结点，？写出推导步骤。 2.写出二叉树先序遍历的非递归算法 3.设计一个算法，输出一棵给定二叉树的 （1）所有叶子节点 （2）叶子节点的个数 4.已知一个二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出该二叉树形表示。 * 数据结构 * lchild 0 0 2 3 7 5 8 0 10 1 data J H F D B A C E G I rchild 0 0 0 9 4 0 0 0 0 0 5、设二叉树bt的存储结构如下： 1 2 3 4 5 6 7 8 9 10 其中，bt为树的根节点指针，lchild、rchild分别为结点的左、 右孩子指针域，在这里使用结点编号作为指针域值， 0表示指针域值为空；data为结点的数据域。 （1）画出二叉树bt的树形表示； （2）写出按先序、中序和后序遍历二叉树bt所得到的结点 序列 （3）画出二叉树bt的后序线索化树。 * 数据结构 * 作业 1、编写递归算法，输出二叉树中从根到叶子结点的所有路径。 2、设给定权集w={2、3、4、7、8、9}，试构造关于w的一棵赫夫曼树，并求其带权路径长度wpl。 用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置。 用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置。 用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置。 * 数据结构 * 例2：【 考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 28 25 40 55 60 33 08 54 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL * 数据结构 * 线索二叉树的生成算法 目的：在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。 为了记下遍历过程中访问结点的先后次序，需要设置两个指针： p指针→当前结点之指针；pre指针→当前结点的前趋结点指针。 设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱），参见算法6.6。 若p-lchild＝NULL,则{p-Ltag=1;p-lchild＝pre;} //p的前驱线索应存p结点的左边 若pre-rchild＝NULL, 则{pre-Rtag＝1; pre-rchild=p;} //pre的后继线索应存pre结点的右边 * 数据结构 * 3. 线索二叉树的遍历（无需堆栈） 对于线索二叉树的遍历，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空为止。 （因为建立线索时已遍历一次，相当于线性化了！） 难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。 以中序线索二叉树为例： 当RTag=1时，直接后继指针就在其rchild域内； 当RTag=0时，直接后继是当前结点右子树最左下方的结点； 请注意中序遍历规则是LDR，先左再根再右 * 数据结构 * 5