河池学院：《数据结构》课程电子教案（PPT教学课件）第7章 树和二叉树 7.3 二叉树先序、中序和后序遍历

二叉树先序、中序和后序遍历7.37.3.1二叉树遍历的概念二叉树遍历是指按照一定次序访问二叉树中所有结点，并且每个结点仅被访问一次的过程。设N为根结点，L、R分别为左、右子树，这6种遍历方法是NLR、LNR、LRN、NRL、RNL、RLN），若再规定先遍历左子树，后遍历右子树，则对于非空二叉树，可得到如下3种递归的遍历方法（即NLR、LNR和LRN）R1/49

二叉树遍历是指按照一定次序访问二叉树中所有结点，并且每个结点仅 被访问一次的过程。 设N为根结点，L、R分别为左、右子树，这6种遍历方法是NLR、LNR、 LRN、NRL、RNL、RLN），若再规定先遍历左子树，后遍历右子树，则对 于非空二叉树，可得到如下3种递归的遍历方法（即NLR、LNR和LRN）。 N L R 1/49

1）先序遍历访问根结点。1先序遍历左子树。先序遍历右子树。3先序序列为：ABDGCEF在一棵二叉树的先序序列中，第一个元素即为根结说明点对应的结点值。2/49

1）先序遍历 ① 访问根结点。 ② 先序遍历左子树。 ③ 先序遍历右子树。 A B C D E F G 先序序列为：ABDGCEF 说明 在一棵二叉树的先序序列中，第一个元素即为根结 点对应的结点值。 2/49

2）中序遍历中序遍历左子树。1访问根结点。中序遍历右子树。3中序序列为：DGBAECF。在一棵二叉树的中序序列中，根结点值将其序列分为前后两部说明分，前部分为左子树的中序序列，后部分为右子树的中序序列。3/49

2）中序遍历 ① 中序遍历左子树。 ② 访问根结点。 ③ 中序遍历右子树。 A B C D E F G 中序序列为：DGBAECF。 说明 在一棵二叉树的中序序列中，根结点值将其序列分为前后两部 分，前部分为左子树的中序序列，后部分为右子树的中序序列。 3/49

3）后序遍历后序遍历左子树。1后序遍历右子树。访问根结点。3.后序序列为：GDBEFCA。在一棵二叉树的后序序列中，最后一个元素即为根说明结点对应的结点值。4/49

3）后序遍历 ① 后序遍历左子树。 ② 后序遍历右子树。 ③ 访问根结点。 A B C D E F G 后序序列为：GDBEFCA。 说明 在一棵二叉树的后序序列中，最后一个元素即为根 结点对应的结点值。 4/49

先序、中序和后序遍历递归算法7.3.21）先序遍历的递归算法//先序遍历的递归算法public void PreOrderi(BTreeclass bt)(Preorder11(bt.b);7//被Preorder1方法调用private void Preorder1i(BTNode t)(if(t!=null)//访问根结点{System.out.print(t.data+"");//先序遍历左子树Preorder11(t.lchild);//先序遍历右子树Preorder1i(t.rchild);5/49

1）先序遍历的递归算法 public void PreOrder1(BTreeClass bt) //先序遍历的递归算法 { PreOrder11(bt.b); } private void PreOrder11(BTNode t) //被PreOrder1方法调用 { if (t!=null) { System.out.print(t.data+ " "); //访问根结点 PreOrder11(t.lchild); //先序遍历左子树 PreOrder11(t.rchild); //先序遍历右子树 } } 5/49

PreOrder116/49

A B C D E F G A B C D E F G PreOrder11 6/49

2）中序遍历的递归算法1/中序遍历的递归算法public void Inorder(BTreeclass bt)tInorder11(bt.b);//被InOrder1方法调用private void InOrder1i(BTNodet){if(t!=null)1/中序遍历左子树Inorder1i(t.lchild);System.out.print(t.data+ " ");1/访问根结点1/中序遍历右子树Inorder1i(t.rchild);7/49

2）中序遍历的递归算法 public void InOrder1(BTreeClass bt) //中序遍历的递归算法 { InOrder11(bt.b); } private void InOrder11(BTNode t) //被InOrder1方法调用 { if (t!=null) { InOrder11(t.lchild); //中序遍历左子树 System.out.print(t.data+ " "); //访问根结点 InOrder11(t.rchild); //中序遍历右子树 } } 7/49

In0rder118/49

A B C D E F G InOrder11 A B C D E F G 8/49

3）后序遍历的递归算法1/后序遍历的递归算法public void Postorder1(BTreeclass bt)tPostorder11(bt.b);?//被Postorder1方法调用privatevoid Postorder11(BTNodet){if(t!=null)1/后序遍历左子树Postorder11(t.lchild);1/后序遍历右子树Postorder11(t.rchild);1/访问根结点System.out.print(t.data+"");9/49

3）后序遍历的递归算法 public void PostOrder1(BTreeClass bt) //后序遍历的递归算法 { PostOrder11(bt.b); } private void PostOrder11(BTNode t) //被PostOrder1方法调用 { if (t!=null) { PostOrder11(t.lchild); //后序遍历左子树 PostOrder11(t.rchild); //后序遍历右子树 System.out.print(t.data+ " "); //访问根结点 } } 9/49

PostOrder1110/49

A B C D E F G PostOrder11 A B C D E F G 10/49