[理学]第六章 树.ppt

后序遍历二叉树的操作定义： 若二叉树为空，则空操作；否则 (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。 后序遍历的顺序为：BCA 后序遍历的顺序为： LEBMIHJDA A B C A B D E L H M I J - - / + × a b c d e f 例：请写出下图所示二叉树的先序、中序和后序遍历顺序。 遍历结果： 先序： - + a×b - c d / e f 中序： a + b×c - d - e / f 后序： a b c d -×+ e f / - 表达式的前缀表示（波兰式） 表达式的中缀表示 表达式的后缀表示（逆波兰式） 先序遍历二叉树基本操作的递归算法在二叉链表上的实现： Status PreOrderTraverse (Bitree T, Visit) { // 最简单的 Visit 函数是： // Status PrintElement (TElemType e) // { Printf (e); // 实用时加上格式串。 // return OK; } // 调用实例：PreOrderTraverse (T, PrintElement); if (T) { if (Visit (T??data)) if (PreOrderTraverse (T??lchild, Visit)) if (PreOrderTraverse (T??rchild, Visit)) return OK; return ERROR; } else return OK; } // PreOrderTraverse lchild data rchild 结点结构 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ T 中序遍历二叉树基本操作的递归算法在二叉链表上的实现： Status InOrderTraverse (Bitree T, Visit) { if (T) { if (InOrderTraverse ( T??lchild, Visit )) if (Visit (T??data)) if (InOrderTraverse (T??rchild, Visit)) return OK; return ERROR; } else return OK; } // InOrderTraverse A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ T 后序遍历二叉树基本操作的递归算法在二叉链表上的实现： Status PostOrderTraverse (Bitree T, Visit) { if (T) { if (PostOrderTraverse ( T??lchild, Visit )) if (PostOrderTraverse (T??rchild, Visit)) if (Visit (T??data)) return OK; return ERROR; } else return OK; } // PostOrderTraverse A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ T 以中序遍历为例来说明中序遍历二叉树的递归过程 第一次经过 第二次经过 第三次经过 Ф B D Ф Ф A B C E D ▲ 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种 说法（） （A）正确 （B）错误 由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树，这种说 法（） （A）正确 （B）错误 已知某二