树 二叉树的遍历 2011.pptVIP

第五章 树 二叉树(3) 二叉树的遍历 先序(前序)遍历 先访问根结点，然后分别先序遍历左子树、右子树 中序遍历 先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历 先后序遍历左、右子树，然后访问根结点 层次遍历 从上到下、从左到右访问各结点 先序遍历序列：A B D C 中序遍历序列：B D A C 后序遍历序列：D B C A 内容提要 由遍历序列确定二叉树的问题 线索二叉树 从遍历序列恢复二叉树 能否根据一棵二叉树的某种遍历顺序来唯一地确定这棵二叉树？ 由二叉树的先序和中序序列建树 二叉树的先序序列 abcdefg 二叉树的中序序列 cbdaegf 线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？ 何谓线索二叉树？ 遍历二叉树的结果是求得结点的一个线性序列 何谓线索二叉树？ 二叉树中的空指针场多达n + 1 个。 如何利用这些空指针？ 中序穿线树 后序穿线树 何谓线索二叉树？ 指向该线性序列中的“前驱”和“后继”的指针，称作“线索” 包含 “线索”的存储结构，称作 “线索链表” 与其相应的二叉树，称作 “线索二叉树” 线索二叉树结点定义 对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域 若该结点的左子树不空，则Lchild域的指针指向其左子树且左标志域的值为“指针 Link”否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread” 若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为 “指针 Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”。 如此定义的二叉树的存储结构称作“线索链表” 线索链表的类型描述： typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 class BiThrNod { TElemType data; BiThrNode *lchild, *rchild; // 左右指针 PointerThr LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree; 如何建立线索链表？ 在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的、指针p所指结点的前驱。 带头结点的中序线索化 带头结点的中序线索化（续） 线索链表的遍历算法 由于在线索链表中添加了遍历中得到的前驱”和“后继”的信息，从而简化了遍历的算法 for ( p = firstNode(T); p; p = Succ(p) ) Visit (p); 在中序线索化链表中结点的后继 中序遍历的第一个结点? 左子树上处于“最左下”（没有左子树）的结点 在中序线索化链表中结点的后继? 若无右子树，则为后继线索所指结点 否则为对其右子树进行中序遍历时访问的第一个结点 找某一结点的后继 ThNode *InorderNext(ThNode *ptr) { ThNode *q; If(prt-rtag==Thread) return(ptr-right); else { q=ptr-right; while(q-ltag==Link) q=q-left; return q; } } 遍历中序线索算法描述 1.寻找中序序列的开始结点 2.访问当前结点然后寻找后继 3.重复2直到后继为空. 练习 阅读266-270 编写程序,验证中序线索化和遍历算法 显示的控制 void main(void) { int i; for (i=32;i0;i=i/2) { cout.width(i); coutiendl; } } 大作业 十进制四则运算器 建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法 按给定的表达式建相应二叉树 由表示式建树 先缀表示式-×+a b c / d e 原表达式(a+b)×c –d/e 用先缀表达式-×+a b c / d e的二叉树 分析表达式和二叉树的关系: 基本操作:参见[严陈]pp261 建叶子结点的算法为： voidCrtNode(BiTreeT,char ch) { if(!(T= new BiTNode)) exit(OVERFL