第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料) 方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉树，再用中序遍历方式打印每个 结点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫 曼编码。 方案三：哈夫曼编/译码器的设计与实现 具体内容：参见严题集P149实习5.2要求，或参见自测卷
1 方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉树，再用中序遍历方式打印每个 结点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫 曼编码。 方案三：哈夫曼编/译码器的设计与实现 具体内容：参见严题集P149 实习5.2要求，或参见自测卷 第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料）
第6章树和二叉树 CTree Binary Tree) 6.1 树的基本概念 二叉树的运算 6.2 二叉树 6.3遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用
2 第6章 树和二叉树 （Tree & Binary Tree） 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 二叉树的运算
6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 Traversing Binary Tree 遍历—指按某条搜索路线遍访每个结点且不重复。 常用的有先序、中序和后序遍历，还有层次遍历。 6.3.2线索二叉树 Threaded Binary Tree 用二叉链表法存储包含个结点的二叉树，结点的指针区域中 会有n+1个空指针。 可以用它来存放当前结点的直接前驱和后继等线索，以加快查 找速度
3 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 遍历——指按某条搜索路线遍访每个结点且不重复。 常用的有先序、中序和后序遍历，还有层次遍历。 Traversing Binary Tree 6.3.2 线索二叉树 用二叉链表法存储包含n个结点的二叉树，结点的指针区域中 会有n+1个空指针。 可以用它来存放当前结点的直接前驱和后继等线索，以加快查 找速度。 Threaded Binary Tree
NIL和NULL的值都是0， 例：【2000年计算机考研题】给定 区别何在？ T,请画出与其对应的中序线 在Delphir中NIL用来标 28 记空指针，Nul用来表 示空的Variant型变量 33 NIL 或是ASCII码为0的字符 比如用于标记字符串结 6008 束。 在C/C++中定义的宏 NULL不加区别的包括 了以上两种含义。 解：因为中序遍历序列是：55402560 对应线索树应当按此规律连线，即在原 可见Object Pascal的 语法要比C/C++严谨得 多
4 例：【 2000年计算机考研题】给定如图所示二叉树 T，请画出与其对应的中序线索二叉树。 28 25 40 55 60 33 08 54 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL NIL和NULL的值都是0, 区别何在？ 在Delphi中NIL用来标 记空指针，Null用来表 示空的Variant型变量 或是ASCII码为0的字符， 比如用于标记字符串结 束。 在C/C++中定义的宏 NULL不加区别的包括 了以上两种含义。 可见Object Pascal的 语法要比C/C++严谨得 多
线索二叉树的生成（递归算法见教材P134-135) 设计技巧 依某种顺序遍历二叉树，对悔个结点，判断其左指 针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继)和本结点的左指针（前 驱)，参见算法6.6。 线索二叉树的遍历（无需堆栈） 难点：在线索化二叉树中，并不是每个结点都能 直接找到其后继的，当标志为0时，则需要通过一 定运算才能找到它的后继
5 线索二叉树的生成（递归算法见教材P134-135） 设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指 针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继）和本结点的左指针（前 驱），参见算法6.6。 线索二叉树的遍历（无需堆栈） 难点：在线索化二叉树中，并不是每个结点都能 直接找到其后继的，当标志为0时，则需要通过一 定运算才能找到它的后继