10第六章 树和二叉树(2)

6.3以结点类为基础的二叉树设计6.3.1二叉树结点类classBiTreeNode{privateBiTreeNodeleftChild;privateBiTreeNoderightChild;privateObjectdata;publicBiTreeNode(){leftChild=null;rightChild=null;}publicBiTreeNode(Objectitem,BiTreeNodeleft,BiTreeNoderight){data=item;leftChild=left;rightChild=right;}publicBiTreeNodegetLeft(){returnleftChild;}publicBiTreeNodegetRight(){returnrightChild;}publicObjectgetData(){returndata;}}6.3.2二叉树的遍历1、遍历定义——2、遍历用途——指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。（或指按某条搜索路线遍访每个结点且不重复）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。3、遍历规则———二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系注：“前、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。D、L、R的组合定义了六种可能的遍历方案：DLR,DRL,LDR,RDL,LRD,RLD若限定先左后右，则有三种实现方案：DLRLDRLRD前序遍历中序遍历后序遍历前序遍历（DLR）递归算法为：若二叉树为空则算法结束；否则：（1）访问根结点；（2）前序遍历根结点的左子树；（3）前序遍历根结点的右子树。ADGECFBABDGCEF中序遍历（LDR）递归算法为：若二叉树为空则算法结束；否则：（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。ADGECFBDGBAECF后序遍历（LRD）递归算法为：若二叉树为空则算法结束；否则：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。ADGECFBGDBEFCA层次遍历：按二叉树的层次序列（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。由分析可知，二叉树层序遍历的特点是，即先被访问的父结点的孩子结点先于后被访问的父结点的孩子结点进行访问。这样，如果把已访问的结点放在一个队列中，那么所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。ADGECFBABCDEFG二叉树的层序遍历算法如下：（1）初始化设置一个队列；（2）把根结点指针入队列；（3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）；（3.a）出队列取得当前队头结点，访问该结点；（3.b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列；（3.c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列；（4）结束。虽然二叉树是一种非线性结构，二叉树不能像单链表那样每个结点都有一个惟一的前驱结点和惟一的后继结点，但当对一个二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是线性的，且是惟一的。例1：前序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEDBEACDEBCA口诀：DLR—前序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根ABDEC+*A*/EDCB前序遍历结果+**/ABCDE—前缀表示法中序遍历结果A/B*C*D+E—中缀表示法后序遍历结果AB/C*D*E+—后缀表示法层次遍历结果+*E*D/CAB例2：用二叉树表示算术表达式但是前序（或后序）和中序遍历序列的组合可以惟一确定一棵二叉树。而前序和后序遍历则不能。二叉树的遍历方法和二叉树的结构由于二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，所以一个二叉树的遍历序列不能决定一棵二叉树。已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。分析：①由后序遍历特征，根结点必在后序序列尾部（即A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。已知中序遍历：BDCEAFHG已知后序遍历：DECBHGFA（BDCE）（FHG）（DCE）BFGHCDEAADGECFB前序遍历：ABDGCEF中序遍历：DGBAECFclassVisit{publicvoidprint(Objectitem){Console.Write(item+);}}访问结点：在二叉树遍历算法中，“访问该结点”表示遍历到二叉树的某个结点时，对该结点进行的具体操作。这样的具体操作会随着问题的不同而不同。二叉树遍历操作的实现classTraverse{publicstaticvoidpreOrder(BiTreeNodet,Visitvs){//前序遍历二叉树t，访问结点操作为vs.print(t.data)if(t!=null){vs.print(t.data);preOrder(t.getLeft(),vs);preOrder(t.getRight(),vs);}}publicstaticvoidinOrder(BiTreeNodet,Visitvs){//中序遍历二叉树t，访问结点操作为vs.print(t.data)if(t!=null){inOrder(t.getLeft(),vs);vs.print(t.data);inOrder(t.getRight(),vs);}}publicstaticvoidpostOrder(BiTreeNodet,Visitvs){//后序遍历二叉树t，访问结点操作为vs.print(t.data)if(t!=null){postOrder(t.getLeft(),vs);postOrder(t.getRight(),vs);vs.print(t.data);}}publicstaticvoidlevelOrder(BiTreeNodet,Visitvs){//层序遍历二叉树t，访问结点操作为vs.print(t.data)LinQueueq=newLinQueue();if(t==null)return;BiTreeNodecurr;q.append(t);while(q.notEmpty()){curr=(BiTreeNode)q.delete();vs.print(curr.data);if(curr.getLeft()!=null)q.append(curr.getLeft());if(curr.getRight()!=null)q.append(curr.getRight());}}练习ABCDEFGHABCDEFGH给出下图所示二叉树的前序遍历、中序遍历、后序遍历和层次遍历的结点序列。前序遍历序列：ABDEGCFH前序遍历序列：ABCEFDGH中序遍历序列：DBGEAFHC后序遍历序列：DGEBHFCA层次遍历序列：ABCDEFGH中序遍历序列：ECFBGDHA后序遍历序列：EFCGHDBA层次遍历序列：ABCDEFGH画出和下列已知结点序列对应的二叉树：（1）该二叉树的中序遍历结点序列为DCBGEAHFIJK;（2）该二叉树的后序遍历结点序列为DCEGBFHKJIA。ABCDEFGHIJK6.3.3二叉树遍历的应用1打印二叉树把二叉树逆时针旋转90度，按照二叉树的凹入表示法打印二叉树。显然，可把此函数设计成递归函数。由于把二叉树逆时针旋转90度后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。ABCABC--CA--B---F---C---EA---B---G---DADGECFBpublicstaticvoidprintBiTree(BiTreeNoderoot,intlevel){if(root!=null){printBiTree(root.getRight(),level+1);if(level!=0){for(inti=0;i6*(level-1);i++){Console.Write();}Console.Write(---);}Console.WriteLine(root.data);printBiTree(root.getLeft(),level+1);}}ABCprintBiTree(A,0)printBiTree(C,1)printBiTree(C,1)printBiTree(null,2)printBiTree(null,2)输出CprintBiTree(null,2)printBiTree(null,2)输出AprintBiTree(B,1)printBiTree(B,1)printBiTree(null,2)printBiTree(null,2)输出BprintBiTree(null,2)printBiTree(null,2)2查找数据元素在二叉树中查找数据元素操作的要求是：在以t为根结点的二叉树中查找数据元素x，若查找到数据元素x时返回该结点；若查找不到数据元素x时返回空。在二叉树t中查找数据元素x函数可设计成前序遍历函数，即首先在根结点查找，然后在左子树查找，最后在右子树查找。publicstaticBiTreeNodesearch(BiTreeNodet,Objectx){BiTreeNodetemp;if(t==null)returnnull;if(t.getData().Equals(x))returnt;if(t.getLeft()!=null){temp=search(t.getLeft(),x);if(temp!=null)returntemp;}if(t.getRight()!=null){temp=search(t.getRight(),x);if(temp!=null)returntemp;}returnnull;}6.3.4非递归的二叉树遍历算法ADGECFBABDGCEF非递归的前序遍历算法非递归的二叉树前序遍历算法如下：（1）初始化设置一个堆栈；（2）把根结点指针入栈；（3）当堆栈非空时，循环执行步骤（3.a）到步骤（3.c）；（3.a）出栈取得栈顶结点，访问该结点；（3.b）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入栈；（3.c）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入栈；（4）结束。ADGECFBpublicstaticvoidpreOrderNoRecur(BiTreeNoderoot){LinStacks=newLinStack();if(root==null)return;BiTreeNodecurr;s.push(root);while(s.notEmpty()){curr=(BiTreeNode)s.pop();Console.Write(+curr.data);if(curr.getRight()!=null)s.push(curr.getRight());if(curr.getLeft()!=null)s.push(curr.getLeft());}}DHGBAECF非递归的中序遍历算法ADGECFBH非递归的二叉树中序遍历算法如下：（1）初始化设置一个堆栈；（2）把根结点置为当前结点；（3）当堆栈非空时或当前结点非空时，循环执行步骤（3.a）到步骤（3.b）:（3.a）当前结点非空，循环执行步骤（3.a.1）到步骤（3.a.2）（3.a.1）当前结点入栈；（3.a.2）当前结点的左孩子成为当前结点；（3.b）如果堆栈不空，出栈取得栈顶结点成为当前结点，访问该结点，让当前结点的右孩子成为当前结点