从节点之间位置关系的角度来看,二叉树的遍历分为3种。

  1. 前序遍历。
  2. 中序遍历。
  3. 后序遍历。

生成二叉树

树节点类

class TreeNode<T> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;

    TreeNode() {
    }

    TreeNode(T data) {
        this.data = data;
    }
}

生成树

10个节点的树

TreeNode<Integer>[] treeNodes = new TreeNode[10];
 for (int i = 0; i < treeNodes.length; i++) {
     treeNodes[i] = new TreeNode<>(i);
 }
 for (int i = 0; i < 10; i++) {
     if (i * 2 + 1 < 10) {
         treeNodes[i].left = treeNodes[i * 2 + 1];
     }
     if (i * 2 + 2 < 10) {
         treeNodes[i].right = treeNodes[i * 2 + 2];
     }
 }

结果手绘
在这里插入图片描述

先序遍历

前序遍历(DLR,lchild,data,rchild),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问 根结点,然后遍历左子树,最后遍历右子树。

//前序遍历
public static void preOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.data);
    preOrder(node.left);
    preOrder(node.right);
}

中序遍历

中序遍历(LDR)是 二叉树遍历的一种,也叫做 中根遍历、中序周游。在二叉树中,先左后根再右。巧记:左根右。

中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树

 //中序遍历
public static void inorder(TreeNode node) {
    if (node == null)
        return;
    inorder(node.left);
    System.out.println(node.data);
    inorder(node.right);
}

后序遍历

后序遍历(LRD)是 二叉树遍历的一种,也叫做 后根遍历、后序周游,可记做左右根。后序遍历有 递归算法和非递归算法两种。在二叉树中,先左后右再根。巧记:左右根。

后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。

//后序遍历
public static void postOrder(TreeNode node) {
    if (node == null)
        return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.data);
}
最后修改:2021 年 09 月 16 日 05 : 53 PM