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

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

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

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

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

A B C D E F G A B C D E F G PreOrder11 6/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

A B C D E F G InOrder11 A B C D E F G 8/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

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