二叉树的遍历

一、前序遍历

遍历顺序：先前序遍历树根，再前序遍历左子树，再前序遍历右子树

先遍历树根(A)--再遍历左子树(B)--再遍历左子树(D)--(D没有左子树了)再遍历右子树(E)--再遍历左子树(G)--(A没有左子树了)再遍历右子树(C)--(C没有左子树了)再遍历右子树(F) ;故顺序为 A-B-D-E-G-C-F;

 

二、中序遍历

遍历顺序：先中序遍历左子树，再遍历树根，再中序遍历右子树

先遍历左子树(D)--再遍历其父元素(B)--再遍历右子树(E)--再遍历左子树(G)--再遍历树根(A)--(A没有左子树了)再遍历右子树(C)--(C没有左子树了)再遍历右子树(F) ;故顺序为 D-B-G-E-A-C-F;

 

三、后序遍历

遍历顺序：先后序遍历左子树，再后序遍历右子树，再遍历树根

先遍历左子树(D)--再遍历左子树(G)--再遍历其父元素(E)--再遍历其父元素(B)--再遍历右子树(F)--在遍历其父元素(C)--再遍历s树根(A) ;故顺序为 D-G-E-B-F-C-A;

代码实现：

定义树节点 TreeNode.java

package interview.tree;

public class TreeNode {
  private final char value;
  private TreeNode left;
  private TreeNode right;
  private TreeNode parent;

  public TreeNode(char value) { //定义树的节点
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
  } 

  public char getValue() {
    return value;
  }

  public TreeNode getLeft() {
    return left;
  }

  public void setLeft(TreeNode left) {
    this.left = left;
    if (this.left != null) {
      this.left.setParent(this);
    }
  }

  public TreeNode getRight() {
    return right;
  }

  public void setRight(TreeNode right) {
    this.right = right;
    if (this.right != null) {
      this.right.setParent(this);
    }
  }

  public TreeNode getParent() {
    return parent;
  }

  private void setParent(TreeNode parent) {
    this.parent = parent;
  }
}

定义二叉树 TreeCreater.java

package interview.tree;

public class TreeCreator {	//使用Node创建树
  public TreeNode createSampleTree() {
    TreeNode root = new TreeNode('A');
    root.setLeft(new TreeNode('B'));
    root.getLeft().setLeft(new TreeNode('D'));
    root.getLeft().setRight(new TreeNode('E'));
    root.getLeft().getRight().setLeft(new TreeNode('G'));
    root.setRight(new TreeNode('C'));
    root.getRight().setRight(new TreeNode('F'));
    return root;
  }

  public TreeNode createTree(String preOrder, String inOrder) {
    if (preOrder.isEmpty()) {
      return null;
    }

    char rootValue = preOrder.charAt(0);
    int rootIndex = inOrder.indexOf(rootValue);

    TreeNode root = new TreeNode(rootValue);
    root.setLeft(
        createTree(
            preOrder.substring(1, 1 + rootIndex),
            inOrder.substring(0, rootIndex)));
    root.setRight(
        createTree(
            preOrder.substring(1 + rootIndex),
            inOrder.substring(1 + rootIndex)));

    return root;
  }
}

定义遍历方法：TreeTraversal.java

package interview.tree;

public class TreeTraversal {

  public void preOrder(TreeNode root) {	//【前序遍历】
    if (root == null) {		//树为空的情况
      return;
    }
    System.out.print(root.getValue());	//先遍历树根
    preOrder(root.getLeft());	//再前序遍历左子树
    preOrder(root.getRight());	//再前序遍历右子树
  }

  public void inOrder(TreeNode root) {//【中序遍历】
    if (root == null) {
      return;
    }
    inOrder(root.getLeft());//先前序遍历左子树
    System.out.print(root.getValue());//再遍历树根
    inOrder(root.getRight());//再前序遍历右子树
  }

  public void postOrder(TreeNode root) {//【后序遍历】
    if (root == null) {
      return;
    }
    postOrder(root.getLeft());//先后序遍历左子树
    postOrder(root.getRight());//再后序遍历右子树
    System.out.print(root.getValue());//再遍历树根
  }

  public static void main(String[] args) {
    TreeCreator creator = new TreeCreator();
    TreeTraversal traversal = new TreeTraversal();

    
    TreeNode sampleTree = creator.createSampleTree();
    traversal.preOrder(sampleTree);
    System.out.println();
    traversal.inOrder(sampleTree);
    System.out.println();
    traversal.postOrder(sampleTree);
    System.out.println();

    
  }
}

输出：

例1. 由前序和中序遍历求出后序遍历

分析：

TreeTraversal.java

package interview.tree;

public class TreeTraversal {

  public void preOrder(TreeNode root) {	//【前序遍历】
    if (root == null) {		//树为空的情况
      return;
    }
    System.out.print(root.getValue());	//先遍历树根
    preOrder(root.getLeft());	//再前序遍历左子树
    preOrder(root.getRight());	//再前序遍历右子树
  }

  public void inOrder(TreeNode root) {//【中序遍历】
    if (root == null) {
      return;
    }
    inOrder(root.getLeft());//先前序遍历左子树
    System.out.print(root.getValue());//再遍历树根
    inOrder(root.getRight());//再前序遍历右子树
  }

  public void postOrder(TreeNode root) {//【后序遍历】
    if (root == null) {
      return;
    }
    postOrder(root.getLeft());//先后序遍历左子树
    postOrder(root.getRight());//再后序遍历右子树 
    System.out.print(root.getValue());//再遍历树根
  }

  public String postOrder(String preOrder, String inOrder) {	//【新增代码】例1，查找后续遍历
    if (preOrder.isEmpty()) {	//树为空时
      return "";
    }

    char rootValue = preOrder.charAt(0);	//拿出前序遍历的第一个点
    int rootIndex = inOrder.indexOf(rootValue);//在中序遍历中找到 A 即可分出左右树

    return  //不用建树，直接输出
        postOrder(
            preOrder.substring(1, 1 + rootIndex),//左子树前序遍历的区间
            inOrder.substring(0, rootIndex)) +	//左子树中序遍历的区间
        postOrder(
            preOrder.substring(1 + rootIndex),//右子树前序遍历的区间
            inOrder.substring(1 + rootIndex)) +//右子树中序遍历的区间
        rootValue;
  }

  public static void main(String[] args) {
    TreeCreator creator = new TreeCreator();
    TreeTraversal traversal = new TreeTraversal();

    System.out.println("Sample tree traversal");
    System.out.println("=====");
    TreeNode sampleTree = creator.createSampleTree();
    traversal.preOrder(sampleTree);
    System.out.println();
    traversal.inOrder(sampleTree);
    System.out.println();
    traversal.postOrder(sampleTree);
    System.out.println();

    System.out.println("=====");
    System.out.println("Creating tree from preOrder and inOrder");
    System.out.println("=====");
    TreeNode tree = creator.createTree("ABDEGCF", "DBGEACF");
    traversal.postOrder(tree);
    System.out.println();
    traversal.postOrder(creator.createTree("", "")); //空树
    System.out.println();
    traversal.postOrder(creator.createTree("A", "A"));//单节点
    System.out.println();
    traversal.postOrder(creator.createTree("AB", "BA"));//双节点
    System.out.println();

    System.out.println("=====");
    System.out.println("Generating postOrder directly");
    System.out.println("=====");
    System.out.println(
        traversal.postOrder("ABDEGCF", "DBGEACF"));
    System.out.println(
        traversal.postOrder("", ""));
    System.out.println(
        traversal.postOrder("A", "A"));
    System.out.println(
        traversal.postOrder("AB", "BA"));
  }
}

输出：

二、寻找中序遍历时的下一节点

将中序遍历由递归改为非递归，遍历顺序：

 

寻找中序遍历时的下一节点用处：对搜索树做中序遍历，得到有序序列；

思路：

代码实现：InOrder.java

package interview.tree;

public class InOrder {	//定义中序遍历

  public TreeNode next(TreeNode node) {
    if (node == null) {
      return null;
    }

    if (node.getRight() != null) {	//右子树不为空，
      return first(node.getRight());//则返回右子树第一个节点
    } else {		//右子树为空,往上走
      while(node.getParent() != null
          && node.getParent().getRight() == node) {
        node = node.getParent();
      }
      // now we have:
      // node.getParent() == null
      // || node is left child of its parent
      return node.getParent();
    }
  }

  public TreeNode first(TreeNode root) {
    if (root == null) {
      return null;
    }

    TreeNode curNode = root;
    while(curNode.getLeft() != null) {
      curNode = curNode.getLeft();
    }
    return curNode;
  }

  public void traverse(TreeNode root) {
    for (TreeNode node = first(root);
        node != null;
        node = next(node)) {
      System.out.print(node.getValue());
    }
    System.out.println();
  }

  public static void main(String[] args) {
    TreeCreator creator = new TreeCreator();
    InOrder inOrder = new InOrder();

    TreeNode sampleTree = creator.createSampleTree();
    inOrder.traverse(sampleTree);

    inOrder.traverse(creator.createTree("", ""));
    inOrder.traverse(creator.createTree("A", "A"));
    inOrder.traverse(creator.createTree("AB", "BA"));
    inOrder.traverse(creator.createTree("ABCD", "DCBA"));
    inOrder.traverse(creator.createTree("ABCD", "ABCD"));
  }
}

输出：

例3

分析：后序遍历则最后一个为树根，二叉查找树中，左子树要比树根小，右子树要比树根大；所以序列中，前面一部分数字要比根要小，后面一部分数组要比根大，A 中 树根最大，则其没有右子树，只有左子树；B，3 和 5 是其右子树，1 是其左子树，但要先遍历左子树，故 B 不是；C 显然可以；D 与 A 相反，它只有右子树；故选 B

 

算法复杂度

代表最坏情况用时；

1.

2.

3.