算法与数据结构第6章2.ppt

第6章 树和二叉树（ Tree Binary Tree ） 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 2. 二叉树的性质 (3+2) 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： 课堂讨论： 4. 二叉树的存储结构 讨论：不是完全二叉树怎么办？ 二、链式存储结构用二叉链表即可方便表示。 例： 6.3 遍历二叉树和线索二叉树 例1： 例2：用二叉树表示算术表达式 遍历的算法实现：用递归形式格外简单！ 先序遍历算法 DLR( liuyu *root ) {if (root !=NULL) //非空二叉树 {printf(“%d”,root-data); //访问D DLR(root-lchild); //递归遍历左子树 DLR(root-rchild); //递归遍历右子树 } return(0); } 对遍历的分析： 例：【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。 注：要实现遍历运算必须先把二叉树存入机内。 习题讨论： 3 中序遍历的非递归(迭代)算法 特别讨论：若已知先序/后序遍历结果和中序遍历结果，能否“恢复”出二叉树？ 【严题集6.31④】 证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。 中序遍历：B D C E A F H G后序遍历：D E C B H G F A 问：用二叉链表法（l_child, r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？ 分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说明）。 除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n－1个结点的链域存放指针，指向非空子女结点（即直接后继）。 二、线索二叉树（Threaded Binary Tree） 规 定： 有关线索二叉树的几个术语： 例1：带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。 例2：画出以下二叉树对应的中序线索二叉树。 4.【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 作 业 附：中序遍历迭代算法(利用堆栈) 附：层序遍历算法(利用队列) 1. 完成第6章自测卷有关内容，算法设计题一定要写出思路。 2. 预习实验：Huffman 编/译码器的设计与实现 (实验要求详见严题集P149 ) void iter_inorder(tree_pointer node) { int top= -1; /* initialize stack */ tree_pointer stack[MAX_STACK_SIZE]; for (;;) { for (; node; node=node-left_child) add(top, node);/* add to stack */ node= delete(top); /* delete from stack */ if (!node) break; /* empty stack */ printf(“%D”, node-data); node = node-right_child; } } 时间复杂度O(n) void level_order(tree_pointer ptr) /* level order tree traversal */ { int front = rear = 0; tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; /* empty queue */ addq(front, rear, ptr); for (;;) { ptr = deleteq(front, rear); + * E * D / C A B * 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 （今日授课内容是本章及本课程的重点） 上机内容： Huffman 编/译码器的设计与实现 （实验要求参见严题集P149 ） 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构 （二叉树的运算见下一节） 性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。 性质2: 深度为k的二叉树至多有2k-1个结点（k0）。 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2