课程名称：数据结构第11周，第11讲次摘 要第六章树和二叉树授课题目（章、节）第三节以结点类为基础的二叉树设计【目的要求】通过本讲课程的学习，了解基于结点类的二叉树设计方法，掌握二叉树的遍历算法。【重点】二叉树的遍历算法。【难点】二叉树的遍历算法。内容【本讲课程的引入】上一次课我们讲到过二叉树的存储最常用的是二叉链存储结构，那么在二叉链存储下，一个二叉树是由若于个结点构成的，因此在二叉树的设计之前必须先设计结点类，下面我们来看一下结点类的设计方法。【本讲课程的内容】6.3以结点类为基础的二叉树设计6.3.1二叉树结点类public class BiTreeNodeprivate BiTreeNode leftChild;private BiTreeNode rightChild;public Object data;BiTreeNodeOfleftChild = null;rightChild = null:子BiTreeNode(Object item, BiTreeNode left,BiTreeNode right){data = item;leftChild = left;rightChild = right;1public BiTreeNode getLeft O(return leftChild:1public BiTreeNode getRight{return rightChild;1public ObjectgetData(return data;16.3.22二叉树的遍历1.，相关概念（1）遍历定义一指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅-被访问一次。（或指按某条搜索路线遍访每个结点且不重复）
课程名称：数据结构 第 11 周，第 11 讲次 摘 要 授课题目（章、节） 第六章 树和二叉树 第三节 以结点类为基础的二叉树设计 【目的要求】通过本讲课程的学习，了解基于结点类的二叉树设计方法，掌握二叉树的遍历算法。 【重 点】二叉树的遍历算法。 【难 点】二叉树的遍历算法。 内 容 【本讲课程的引入】上一次课我们讲到过二叉树的存储最常用的是二叉链存储结构，那么 在二叉链存储下，一个二叉树是由若干个结点构成的，因此在二叉树的设计之前必须先设 计结点类，下面我们来看一下结点类的设计方法。 【本讲课程的内容】 6.3 以结点类为基础的二叉树设计 6.3.1 二叉树结点类 public class BiTreeNode{ private BiTreeNode leftChild; private BiTreeNode rightChild; public Object data; BiTreeNode(){ leftChild = null; rightChild = null; } BiTreeNode(Object item, BiTreeNode left, BiTreeNode right){ data = item; leftChild = left; rightChild = right; } public BiTreeNode getLeft(){ return leftChild; } public BiTreeNode getRight(){ return rightChild; } public Object getData(){ return data; } } 6.3.2 二叉树的遍历 1.．相关概念 （1）遍历定义——指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅 被访问一次。（或指按某条搜索路线遍访每个结点且不重复）
（2）遍历用途一一它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。（3）遍历方法一一对每个结点的查看通常都是“先左后右”。（4）遍历规则一一二叉树由根、左子树、右子树构成，定义为D、L、RD、L、R的组合定义了六种可能的遍历方案：DLR，DRL，LDR，RDL，LRD，RLD若限定先左后右，则有三种实现方案：DLR（前序遍历）、LDR（中序遍历）、LRD（后序遍历）注：“前、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。2.遍历算法分别来看一下这三种遍历方法：（1）前序遍历（DLR）递归算法为：若二叉树为空则算法结束：否则：（1）访问根结点：（2）前序遍历根结点的左子树：（3）前序遍历根结点的右子树。（2）中序遍历（LDR）递归算法为：若二叉树为空则算法结束；否则：（1）中序遍历根结点的左子树：（2）访问根结点：（3）中序遍历根结点的右子树。（3）后序遍历（LRD）递归算法为：若二叉树为空则算法结束：否则：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。（4）层次遍历：按二叉树的层次序列（即从根结点层至叶节点层），同一层中按先左子树再右子树的次序遍历二叉树。由分析可知，二叉树层序遍历的特点是，即”先被访问的父结点的孩子结点”先于”后被访问的父结点的孩子结点“进行访问。这样，如果把已访问的结点放在一个队列中，那么所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。二叉树的层序遍历算法如下：（1）初始化设置一个队列；（2）把根结点指针入队列：（3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）；（3.a）出队列取得当前队头结点，访问该结点：（3.b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列：（3.c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列：（4）结束。虽然二叉树是一种非线性结构，二叉树不能像单链表那样每个结点都有一个惟一的前驱结点和惟一的后继结点，但当对一个二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是线性的，且是惟一的
（2）遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切 运算的基础和核心。 （3）遍历方法——对每个结点的查看通常都是“先左后右” 。 （4）遍历规则——二叉树由根、左子树、右子树构成，定义为 D、 L、R D、L、R 的组合定义了六种可能的遍历方案：DLR, DRL, LDR, RDL, LRD, RLD 若限定先左后右，则有三种实现方案：DLR（前序遍历）、LDR（中序遍历）、LRD（后序遍历） 注：“前、中、后”的意思是指访问的结点 D 是先于子树出现还是后于子树出现。 2．遍历算法 分别来看一下这三种遍历方法： （1）前序遍历（DLR）递归算法为： 若二叉树为空则算法结束；否则： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。 （2）中序遍历（LDR）递归算法为： 若二叉树为空则算法结束；否则： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 （3）后序遍历（LRD）递归算法为： 若二叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 （4）层次遍历：按二叉树的层次序列（即从根结点层至叶节点层），同一层中按先左子树 再右子树的次序遍历二叉树。 由分析可知，二叉树层序遍历的特点是，即"先被访问的父结点的孩子结点"先于"后被 访问的父结点的孩子结点"进行访问。这样，如果把已访问的结点放在一个队列中，那么所 有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此 可以借助队列实现二叉树的层序遍历。 二叉树的层序遍历算法如下： （1）初始化设置一个队列； （2）把根结点指针入队列； （3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得当前队头结点，访问该结点； （3.b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列； （3.c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列； （4）结束。 虽然二叉树是一种非线性结构，二叉树不能像单链表那样每个结点都有一个惟一的前 驱结点和惟一的后继结点，但当对一个二叉树用一种特定的遍历方法来遍历时，其遍历序 列一定是线性的，且是惟一的
3.二叉树的遍历方法和二叉树的结构由于二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，所以一个二叉树的遍历序列不能决定一棵二叉树。但是前序（或后序）和中序遍历序列的组合可以惟确定一棵二叉树。而前序和后序遍历则不能。已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。分析：①由后序遍历特征，根结点必在后序序列尾部（即A）：②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）：③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。最后得到的二叉树如下图所示A-A4.访问结点在二叉树遍历算法中，“访问该结点”表示遍历到二叉树的某个结点时，对该结点进行的具体操作。这样的具体操作会随着问题的不同而不同。public class Visit(public void print(Object item)(System.out.print(item +"");115.二叉树遍历操作的实现public class Traversefpublic static voidpreOrder(BiTreeNode t,Visitvs)(//前序遍历二叉树t，访问结点操作为vs.print（t.data)if(t = null)(vs. print (t. data) ;preOrder(t. getLeft O, vs) ;preOrder(t.getRight O,vs);]publicstaticvoidinOrder(BiTreeNodet,Visitvs)(//中序遍历二叉树t，访间结点操作为vs.print（t.data)if(t /= null) (inOrder(t.getLeftO,vs);vs.print(t.data):inOrder(t.getRightO,vs);11
3．二叉树的遍历方法和二叉树的结构 由于二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，所以一个二叉 树的遍历序列不能决定一棵二叉树。但是前序（或后序）和中序遍历序列的组合可以惟一 确定一棵二叉树。而前序和后序遍历则不能。 已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二 叉树。 分析： ①由后序遍历特征，根结点必在后序序列尾部（即 A）； ②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即 BDCE）， 其右部必全部是右子树的子孙（即 FHG）； ③继而，根据后序中的 DECB 子树可确定 B 为 A 的左孩子，根据 HGF 子串可确定 F 为 A 的右 孩子；以此类推。 最后得到的二叉树如下图所示 4.访问结点 在二叉树遍历算法中，“访问该结点”表示遍历到二叉树的某个结点时，对该结点进 行的具体操作。这样的具体操作会随着问题的不同而不同。 public class Visit{ public void print(Object item){ System.out.print(item + " "); } } 5．二叉树遍历操作的实现 public class Traverse{ public static void preOrder(BiTreeNode t, Visit vs){ //前序遍历二叉树 t，访问结点操作为 vs.print(t.data) if(t != null){ vs.print(t.data); preOrder(t.getLeft(),vs); preOrder(t.getRight(),vs); } } public static void inOrder(BiTreeNode t, Visit vs){ //中序遍历二叉树 t，访问结点操作为 vs.print(t.data) if(t != null){ inOrder(t.getLeft(),vs); vs.print(t.data); inOrder(t.getRight(),vs); } }
public staticvoidpostOrder(BiTreeNodet,Visitvs)(//后序遍历二叉树t，访问结点操作为vs.print（t.data）if(t!=null)(postOrder(t.getLeftO,vs);postOrder(t.getRightO,vs);vs. print(t. data) ;11public static void levelOrder(BiTreeNode t, Visit vs) throws Exceptionf//层序遍历二叉树t，访问结点操作为vs.print（t.data）LinQueue q=newLinQueueO;if(t == null) return;BiTreeNode curr;q.append(t) :while(!q.isEmptyO)(curr=(BiTreeNode)q.deleteO;vs.print(curr.data):if(curr.getLeftO!= null)q.append(curr.getLeft ()):if(curr.getRight O != null)q.append(curr.getRightO);16.3.3二叉树历的应用1打印二叉树把二叉树逆时针旋转90度，按照二叉树的凹入表示法打印二叉树。显然，可把此函数设计成递归函数。由于把二叉树逆时针旋转90度后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。--CA--Bpublic static void printBiTree(BiTreeNode root, int level)(if(root !=null)(printBiTree(root.getRightO,level + 1);if(level != 0)(for(int i=0;i<6*(level-1):i++)fSystem.out.print(""):于System.out. print("---");System.out.println(root.data);printBiTree(root.getLeftO,level + 1):1
public static void postOrder(BiTreeNode t, Visit vs){ //后序遍历二叉树 t，访问结点操作为 vs.print(t.data) if(t != null){ postOrder(t.getLeft(),vs); postOrder(t.getRight(),vs); vs.print(t.data); } } public static void levelOrder(BiTreeNode t, Visit vs) throws Exception{ //层序遍历二叉树 t，访问结点操作为 vs.print(t.data) LinQueue q = new LinQueue(); if(t == null) return; BiTreeNode curr; q.append(t); while(! q.isEmpty()){ curr = (BiTreeNode)q.delete(); vs.print(curr.data); if(curr.getLeft() != null) q.append(curr.getLeft()); if(curr.getRight() != null) q.append(curr.getRight()); } } 6.3.3 二叉树遍历的应用 1 打印二叉树 把二叉树逆时针旋转 90 度，按照二叉树的凹入表示法打印二叉树。显然，可把此函数设计 成递归函数。由于把二叉树逆时针旋转 90 度后，在屏幕上方的首先是右子树，然后是根结 点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。 public static void printBiTree(BiTreeNode root, int level){ if(root != null){ printBiTree(root.getRight(),level + 1); if(level != 0){ for(int i = 0; i < 6 * (level - 1); i ++){ System.out.print(" "); } System.out.print(“-”); System.out.println(root.data); } printBiTree(root.getLeft(),level + 1); } A B C A B C -C A -B
2查找数据元素在二叉树中查找数据元素操作的要求是：在以t为根结点的二叉树中查找数据元素x，若查找到数据元素x时返回该结点：若查找不到数据元素x时返回空。在二叉树t中查找数据元素x函数可设计成前序遍历函数，即首先在根结点查找，然后在左子树查找，最后在右子树查找。public static BiTreeNode search(BiTreeNodet,Objectx)fBiTreeNodetemp;if(t == null) return null;if(t.data.equals(x)) return t;if(t.getLeft O != null)(temp = search(t.getLeftO,x) ;If(temp !=null)return temp;1if(t.getRightO != null)(temp = search(t.getRight(,x);if(temp != null) return temp:7return null;2【本讲课程的小结】二叉树的遍历算法是其他二叉树操作的基础和核心，因此遍历算法是必须要熟练掌握的内容，特别是根据一棵二叉树要能够准确的给出遍历序列，给出前序（后序）和中序遍历序列要求能画出相应的二叉树。【本讲课程的作业】画出和下列已知结点序列对应的二叉树：（1）该二叉树的中序遍历结点序列为DCBGEAHFIJK（2）该二叉树的后序遍历结点序列为DCEGBFHKJIA
} 2 查找数据元素 在二叉树中查找数据元素操作的要求是：在以 t 为根结点的二叉树中查找数据元素 x， 若查找到数据元素 x 时返回该结点；若查找不到数据元素 x 时返回空。 在二叉树 t 中查找数据元素 x 函数可设计成前序遍历函数，即首先在根结点查找，然 后在左子树查找，最后在右子树查找。 public static BiTreeNode search(BiTreeNode t, Object x){ BiTreeNode temp; if(t == null) return null; if(t.data.equals(x)) return t; if(t.getLeft() != null){ temp = search(t.getLeft(),x); If(temp != null) return temp; } if(t.getRight() != null){ temp = search(t.getRight(),x); if(temp != null) return temp; } return null; } 【本讲课程的小结】二叉树的遍历算法是其他二叉树操作的基础和核心，因此遍历算法是 必须要熟练掌握的内容，特别是根据一棵二叉树要能够准确的给出遍历序列，给出前序（后 序）和中序遍历序列要求能画出相应的二叉树。 【本讲课程的作业】 画出和下列已知结点序列对应的二叉树： （1）该二叉树的中序遍历结点序列为 DCBGEAHFIJK;（2）该二叉树的后序遍历结点序列为 DCEGBFHKJIA