数据结构第7章树.pptVIP

树和森林的遍历 深度优先遍历 先根次序遍历 后根次序遍历 广度优先遍历 按层次序遍历 树和森林的遍历 树和森林的遍历 树的存储结构 顺序表示 二叉树的遍历 树的遍历就是按某种次序访问树中的所有结点， 要求每个结点访问一次且仅访问一次。 遍历二叉树三方面工作：访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有： 前序 DLR 镜像 DRL 中序 LDR 镜像 RDL 后序 LRD 镜像 RLD 前序遍历二叉树： 若二叉树非空，则 访问根结点 (D) 前序遍历左子树 (L) 前序遍历右子树 (R) 中序遍历二叉树： 若二叉树非空，则 中序遍历左子树 (L) 访问根结点 (D) 中序遍历右子树 (R) 后序遍历二叉树： 若二叉树非空，则 后序遍历左子树 (L) 后序遍历右子树 (R) 访问根结点 (D) 统计二叉树叶子结点的个数 构造二叉树 由二叉树的前序序列和中序序列 可唯一地确定一棵二叉树。 哈夫曼树 (Huffman Tree) 前序序列 ABHFDECKG 中序序列 HBDFAEKCG HBDF EKCG A EKCG A B H DF ABHFDECKG HBDFAEKCG 右前序 ECKG 中序 EKCG 右前序 ECKG 中序 EKCG EKCG A B H F D KCG E A B H F D 无左 E A B H F D C K G 左前序 BHFD 中序 HBDF 左前序 BHFD 中序 HBDF 左 左 右 前序确定根 中序分左右 建立子树pre[l1..h1]和in[l2..h2]： （1）建立根结点pre[l1] （2）在in[l2..h2]中确定根in[k]=pre[l1] （3）分别建立左右子树， 并将左右孩子的指针填入根结点 利用递归方法建立二叉树 参数？ 出口？ 中序遍历二叉树的非递归算法 a b c d e f 中序遍历LDR 基本思想：保存根结点 遍历左子树 取出根结点 访问根结点 遍历右子树 注：利用栈保存根结点 a 存根 向左 b a 存根 向左 f b a 存根 向左 左 空 b a 取根 访问 向右 右 空 a 取根 访问 向右 d a 存根 向左 左 空 a 取根 访问 向右 右 空 取根 访问 向右 c 存根 向左 e c 存根 向左 f b d a 中序遍历序列： f b d a e c d a e c b f 设活动指针p扫描每个结点 当p!= ? p入栈 p指向其左孩子 当p== ? 出栈p 访问p p指向其右孩子 a b c d e f 设活动指针p扫描每个结点 当p!= ? p入栈 p指向其左孩子 当p== ? 出栈p 访问p p指向其右孩子 inorder(BTNode *b) { BTNode *p; init(S); /*栈初始化*/ p=b; for( p!=NULL ) { while(p!=NULL) {push(S,p);/*p入栈*/ p=p-lchild; /*进入左子树*/ } if(empty(S)) return; p=pop(S); /*出栈*/ visite(p); /*访问*/ p=p-rchild; /*进入右子树*/ } } 中序遍历二叉树的非递归算法 按层次遍历二叉树 b a d e c f g 注：利用队列保存结点 遍历序列：a b c d e f g a a a b b b