数据结构课件1第6章树和二叉树New幻灯片.ppt

* 二叉树小结 1、定义和性质 2、存储结构 3、遍历 4、线索化：线索树 顺序结构 链式结构 二叉链表 三叉链表 先序线索树 中序线索树 后序线索树 树 二叉树 森林 中序遍历 后序遍历 先序遍历 霍夫曼树 霍夫曼编码 * 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 附：层序遍历算法(利用队列) * 0 0 A 0 0 C 0 0 B 1 1 E 1 1 F 1 1 G 0 0 D 1 1 I 1 1 H 注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G 0 -- root 0 对应的中序线索二叉树存储结构如图所示： * 例2：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 28 25 40 55 60 33 08 54 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL * 线索二叉树的生成算法（算法6.6, 见教材P134） 目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后 继。 注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针→当前结点之指针； pre指针→前驱结点之指针。 技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针p应当送到前驱结点的空右域中。 若p-lchild＝NULL,则{p-Ltag=1;p-lchild＝pre;} //p的前驱结点指针pre存入左空域 若pre-rchild＝NULL, 则{pre-Rtag＝1;pre-rchild=p;} //p存入其前驱结点pre的右空域 * 3. 线索二叉树的遍历 理论上，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空时结束。 但是，在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，R_child=右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。 以中序线索二叉树为例： 对叶子结点（RTag=1），直接后继指针就在其rchild域内； 对其他结点（RTag=0），直接后继是其右子树最左下的结点； （因为中序遍历规则是LDR，先左再根再右） ① ② ④ ⑧ ⑤ ⑨ ③ ⑥ ⑦ ⑩…… * 程序注解 (非递归，且不用栈）： P=T-lchild; //从头结点进入到根结点； while( p!=T) {while(p-LTag==link)p=p-lchild; //先找到中序遍历起点 if(!visit(p-data)) return ERROR; //若起点值为空则出错告警 while(p-RTag==Thread ……){ p=p-rchild; Visit(p-data);} //若有后继标志，则直接提取p-rchild中线索并访问后继结点； p=p-rchild; //当前结点右域不空或已经找好了后继，则一律从结