(5_2)二叉树的遍历及应用.ppt

数据结构;第五章 树;内容提要;5.4 二叉树的遍历;访问操作的示例;线性结构与非线性结构遍历的区别;树的遍历方式;深度优先遍历;1.前序遍历;前序遍历的递归算法;2.中序遍历;中序遍历的递归算法;3.后序遍历;后序遍历的递归算法;4.层次遍历：广度优先遍历;层次遍历的算法思想; 层序遍历从二叉树的根节点开始， 首先将根节点指针入队， 然后从队头取出一个元素，每取出一个元素，执行两个操作：;A;层序遍历的算法实现;;5.二叉树遍历的应用;（1）后序遍历的应用;后序遍历的应用（续）;1、可以把任意一个算术表达式用一棵二叉树表示;2、对该二叉树分别进行前序、中序和后序遍历，得到以下三种不同形式： （1）前序遍历：+*/a-bcde（前缀表达式，波兰式） （2）中序遍历：a/b-c*d+e（中缀表达式） （3）后序遍历：abc-/d*e+（后缀表达式，逆波兰式）; 例: 表达式 Exp=a*b+(c-d/e)*f; 例: 表达?? Exp=a*b+(c-d/e)*f; 后缀表达式的特点：; 后缀表达式的计算方法：;例：表达式A/(B+C*D)-E的后缀式ABCD*+/E-;（3）前序遍历的应用;利用前序遍历-创建二叉树;创建二叉树示例;templateclass T void BinaryTreeT::CreateBinTree (ifstream in, BinTreeNodeT * subTree) { //以递归方式建立二叉树 T item; if ( !in.eof () ) { //未读完, 读入并建树 in item; //读入根结点的值 if (item != RefValue) { subTree = new BinTreeNodeT(item); //建立根结点 if (subTree == NULL) {cerr “存储分配错!” endl; exit (1);};;6.二叉树的非递归遍历;（1) 非递归前序遍历二叉树;算法实现;;（2) 非递归中序遍历二叉树;算法实现;（3) 非递归后序遍历二叉树;非递归后序遍历示例;算法实现;算法实现（续）; while (continue1 !S.IsEmpty ()) { S.Pop (w); p = w.ptr; switch (w.tag) { //判断栈顶的tag标记 case L: w.tag = R; S.Push (w); continue1 = 0; p = p-rightChild; break; case R: visit (p); break; } } } while (!S.IsEmpty ()); //继续遍历 cout endl; };7.二叉树计数（形态确定）;结论; 例：已知一棵二叉树的前序序列和中序序列分别为ABDEGCFH和DBGEACHF，则该二叉树的后序序列为 ，层序序列为 。; 解答：若二叉树的任意两个节点的值都不相同，则二叉树的前序序列和中序序列可唯一确定一棵二叉树，确定方法如下： （1）根据前序遍历的定义：前序序列的第一个元素必为二叉树的根节点； 根据中序遍历的定义：中序序列的根节点恰为左右子树的中序序列的分界点；根节点前的子序列为左子树的中序序列；根节点后的子序列为右子树的中序序列； （2）根据左子树的中序序列的节点个数，在前序序列中找出左子树的前序序列，剩下的即为右子树的前序序列； （3）然后用相同的办法分别找出左、右子树的根及其左右子树的前序序列和中序序列； （4）依此类推，直至待构造的二叉树的前序序列仅剩一个字母为止。;前序：A B D H I E J C F K G L;二叉树计数;二叉树计数（续1）;例如: 有 3 个数据 { 1, 2, 3 }，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 321，231，213，132，123。 前序序列为 123，中序序列为 312 的二叉树不存在。;有0个, 1个, 2个, 3个结点的不同二叉树如下;计算具有n个结点的不同二叉树的棵数; 2000年南开大学考研题; 2000年西