树和二叉树 - welcome to trusted .ppt

1. 前序遍历 2. 中序遍历 3.后序遍历 4.层序遍历 规则: 若二叉树为空,则空操作返回,否则, 从树的第一层，即根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。 ABCDEFGHI * Huffman Code Construction R S N I E H C U 58 113 144 126 238 270 330 508 838 T D L 81 156 174 A O 31 27 55 71 73 61 65 125 40 41 93 80 76 * Huffman Code Construction 125 Freq 93 80 76 73 71 61 55 41 40 E Char T A O I N R H L D 31 27 C U 65 S 0000 Fixed 0001 0010 0011 0100 0101 0111 1000 1001 1010 1011 1100 0110 110 Huff 000 011 001 1011 1010 1000 1111 0101 0100 11100 11101 1001 838 Total 4.00 3.62 * 应用实例1 集合的表示（了解） S1={0, 6, 7, 8}, S2={1, 4, 9}, S3={2, 3, 5} Two operations considered here Disjoint set union S1 ? S2={0,6,7,8,1,4,9} Find(i): Find the set containing the element i. 3 ? S3, 8 ? S1 0 6 7 8 1 4 9 2 3 5 Si ? Sj = ? * Disjoint Set Union（不相交集合的并操作） 1 4 9 0 6 7 8 1 4 9 0 6 7 8 Possible representation for S1 union S2 Make one of trees a subtree of the other * 0 6 7 8 4 1 9 2 3 5 *Data Representation of S1S2and S3 * Array Representation for Set int find1(int i) { for (; parent[i]=0; i=parent[i]); return i; } void union1(int i, int j) { parent[i]= j; } * *Trees obtained using the weighting rule weighting rule for union(i,j): if # of nodes in i # in j then j the parent of i * Trees achieving worst case bound ? log28?+1 * 0 1 2 4 3 5 6 7 0 1 2 4 3 5 6 7 查找并做路径压缩 * 本章小结 ? 知识点 – 树、二叉树、二叉树的基本性质 – 二叉树上的操作 – 存储、遍历 – 线索二叉树 – 建立线索、遍历 – 树和森林的基本操作 – 存储、与二叉树的转换 – Huffman树 – 建立、应用 85 * 本章小结 1、定义和性质 2、存储结构 3、遍历 4、线索化：线索树 顺序结构 链式结构 二叉链表 线索链表 先序线索树 中序线索树 后序线索树 树 二叉树 森林 先 序 遍 历 后 序 遍 历 遍历 存储结构 遍历 双亲表示 孩子表示 孩子兄弟 先序遍历 后序遍历 中序遍历 后序遍历 先序遍历 哈夫曼树 哈夫曼编码 * 　1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 　 2. 熟悉二叉树的各种存储结构的特点及适用范围。 　 3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种有哪些信誉好的足球投注网站策略进行的遍历。 本章需要掌握的内容 * 　　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。 * 　　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　　6. 学会编写实现树的