二叉树四种遍历方式，前中后序遍历按照根节点的访问顺序命名

1. 前序遍历：根节点-》左子树-》右子树
2. 中序遍历：左子树-》根节点-》右子树
3. 后序遍历：左子树-》右子树-》根节点
4. 平行序遍历

源码地址：https://github.com/GallantKong/tree.git

案例数据

  /**
   * 案例数据：
   *            15
   *        /        \
   *      10          20
   *     /    \      /    \
   *    8     13    18     25
   *   /  \
   * 7     9
   * @param args :
   */
  public static void main(String[] args) {
    AvlNode<Integer> node = SimpleAvlTree.insert(20, null);
    node = SimpleAvlTree.insert(25, node);
    node = SimpleAvlTree.insert(15, node);
    node = SimpleAvlTree.insert(18, node);
    node = SimpleAvlTree.insert(10, node);
    node = SimpleAvlTree.insert(13, node);
    node = SimpleAvlTree.insert(8, node);
    node = SimpleAvlTree.insert(7, node);
    node = SimpleAvlTree.insert(9, node);
    preorderTraversal(node, null);
    System.out.println("------------------------");
    inorderTraversal(node, null);
    System.out.println("------------------------");
    postorderTraversal(node, null);
  }

前序遍历

代码

  /**
   * 前序遍历（DLR）D=Degree L=left R=right
   * 或 NLR N=Node L=left R=right
   * @param root : 根节点
   */
  private static void preorderTraversal(AvlNode<Integer> root, Boolean isLeft) {
    if (root == null) {
      return;
    }
    System.out.println((isLeft != null ? (isLeft ? "left:" : "right:") : "root:") + root);
    preorderTraversal(root.getLeft(), true);
    preorderTraversal(root.getRight(), false);
  }

执行结果

root:AvlNode{height=3, data=15}
left:AvlNode{height=2, data=10}
left:AvlNode{height=1, data=8}
left:AvlNode{height=0, data=7}
right:AvlNode{height=0, data=9}
right:AvlNode{height=0, data=13}
right:AvlNode{height=1, data=20}
left:AvlNode{height=0, data=18}
right:AvlNode{height=0, data=25}

中序遍历

代码

  /**
   * 中序遍历（LDR）D=Degree L=left R=right
   * 或 LNR N=Node L=left R=right
   * @param root : 根节点
   */
  private static void inorderTraversal(AvlNode<Integer> root, Boolean isLeft) {
    if (root == null) {
      return;
    }
    inorderTraversal(root.getLeft(), true);
    System.out.println((isLeft != null ? (isLeft ? "left:" : "right:") : "root:") + root);
    inorderTraversal(root.getRight(), false);
  }

执行结果

left:AvlNode{height=0, data=7}
left:AvlNode{height=1, data=8}
right:AvlNode{height=0, data=9}
left:AvlNode{height=2, data=10}
right:AvlNode{height=0, data=13}
root:AvlNode{height=3, data=15}
left:AvlNode{height=0, data=18}
right:AvlNode{height=1, data=20}
right:AvlNode{height=0, data=25}

后序遍历

代码

  /**
   * 后序遍历（LRD）D=Degree L=left R=right
   * 或 LRN N=Node L=left R=right
   * @param root : 根节点
   */
  private static void postorderTraversal(AvlNode<Integer> root, Boolean isLeft) {
    if (root == null) {
      return;
    }
    postorderTraversal(root.getLeft(), true);
    postorderTraversal(root.getRight(), false);
    System.out.println((isLeft != null ? (isLeft ? "left:" : "right:") : "root:") + root);
  }

执行结果

left:AvlNode{height=0, data=7}
right:AvlNode{height=0, data=9}
left:AvlNode{height=1, data=8}
right:AvlNode{height=0, data=13}
left:AvlNode{height=2, data=10}
left:AvlNode{height=0, data=18}
right:AvlNode{height=0, data=25}
right:AvlNode{height=1, data=20}
root:AvlNode{height=3, data=15}

平行序遍历

逻辑与之前写过的“之字形遍历”类型，不再赘述
https://blog.csdn.net/u010597819/article/details/116572470

总结

前序/中序/后序遍历是否让你联想起图结构的深度优先遍历？平行序遍历是否联想起图结构的广度优先遍历？如果将一个完整的平衡二叉树转换下是否是一个“邻接矩阵”的图呢？像下面这样，只是矩阵的水平节点最大长度为2
二者的原理是相同的

1. 前中后序遍历顺序：由远到近
2. 平行序遍历顺序：由近到远

图遍历

1. 深度优先遍历：由远到近
2. 广度优先遍历：由近到远

           15
       /        \
     10          20
    /    \      /    \
   8     13    18     25
  /  \
7     9

15->10->20
10->8->13
8->7->9
20->18->25