Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia P为前驱结点。后继节点的方法与上面差不多。 掌握遍历线索二叉树的方法:例如中序线索二叉树,先找到第一个结点(最左边无左 孩子的结点),然后按照上述方法依次寻找后继结点 9)哈夫曼树 概念:没有度为1的结点的二叉树 掌握构造哈夫曼树的数学构造方法。 哈夫曼编码(左0右1) 练习题 1.确定一棵二叉树必须有中序遍历,再加上一种其他遍历。 2.先序 ABDECFGH中序 DEBAFCHG求叶子结点。EFH 3.二叉树链式结构的三种表示法:双亲,孩子,孩子兄弟表示法 4.先序 ABCDEFG中序 BDCAFGE,则先序 EACBDGF 5.若一个叶子是某中序遍历的最后一个,则它是该子树先序遍历的最后一个( right) 若一个结点是某中序遍历的最后一个,则它是该子树先序遍历的最后一个(wong) 哈夫曼树19个结点,则叶子结点10个。 7.N个节点用二叉链表存储,共有N+1个空链域。用了N-1个链域。 大题 1.求一棵二叉树的深度 2.求任意两个结点的最近共同祖先 3.层次遍历算法 4.先序 FAMBXCR中序 AFXBMCR,画出二叉树和后序线索二叉树。后序 ( AXBRCMF),再线索化 5.W={ ABCDEFG},权为{1l,14,8,6,13,22,18,26} 构造W的哈夫曼树,并求出WPL。(118) 写出字符哈夫曼编码。 A=010D=1011 G=111 B=100E=011 C=1010 F=110 第七章图 本章是考试的一个重点,很多应用内容都会涉及到! 图的基本概念 图的存储结构:1)数组表示法,邻接矩阵 2)邻接表及逆邻接表 图的遍历 1)深度优先,类似于二叉树的先序遍历 2)广度优先,类似于树的层次遍历 图的应用:1)最小生成树Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia P 为前驱结点。后继节点的方法与上面差不多。 掌握遍历线索二叉树的方法：例如中序线索二叉树，先找到第一个结点（最左边无左 孩子的结点），然后按照上述方法依次寻找后继结点。 9）哈夫曼树 概念：没有度为 1 的结点的二叉树 掌握构造哈夫曼树的数学构造方法。 哈夫曼编码（左 0 右 1） 练习题 1．确定一棵二叉树必须有中序遍历，再加上一种其他遍历。 2．先序 ABDECFGH,中序 DEBAFCHG, 求叶子结点。EFH 3．二叉树链式结构的三种表示法：双亲，孩子，孩子兄弟表示法。 4．先序 ABCDEFG,中序 BDCAFGE,则先序 EACBDGF。 5．若一个叶子是某中序遍历的最后一个，则它是该子树先序遍历的最后一个（right）。 若一个结点是某中序遍历的最后一个，则它是该子树先序遍历的最后一个（wrong）。 6．哈夫曼树 19 个结点，则叶子结点 10 个。 7．N 个节点用二叉链表存储，共有 N+1 个空链域。用了 N-1 个链域。 大题： 1．求一棵二叉树的深度。 2．求任意两个结点的最近共同祖先。 3．层次遍历算法。 4．先序 FAMBXCR,中序 AFXBMCR，画出二叉树和后序线索二叉树。后序 （AXBRCMF），再线索化。 5．W={ABCDEFG}，权为{11，14，8，6，13，22，18，26} 构造 W 的哈夫曼树，并求出 WPL。（118） 写出字符哈夫曼编码。 A=010 D=1011 G=111 B=100 E=011 C=1010 F=110 H=00 第七章 图 本章是考试的一个重点，很多应用内容都会涉及到！ 图的基本概念。 图的存储结构：1）数组表示法，邻接矩阵 2）邻接表及逆邻接表 图的遍历 ：1）深度优先，类似于二叉树的先序遍历 2）广度优先，类似于树的层次遍历 图的应用 ：1）最小生成树