数据结构 —— 树4种遍历，java代码实现

文章目录

• • 1、树的遍历分类
  • 2、树的遍历
  • • 2.1、定义节点
  • 3、深度优先（DFS）
  • • 3.1、前序遍历
    • 3.2、中序遍历
    • 3.3、后序遍历
  • 4、广度优先（BFS）
  • • 4.1、层次遍历
  • 5、完整代码：

1、树的遍历分类

树的遍历分为两类：

• 深度优先（DFS）
  • 前序遍历
  • 中序遍历
  • 后序遍历
• 广度优先（BFS）
  • 层次遍历

2、树的遍历

2.1、定义节点

public class TreeNode {

    String value = null; // 根节点
    TreeNode leftChildren = null; // 左子节点
    TreeNode rightChildren = null; // 右子节点

    public TreeNode(String value, TreeNode leftChildren, TreeNode rightChildren) {
        this.value = value;
        this.leftChildren = leftChildren;
        this.rightChildren = rightChildren;
    }

    public TreeNode(String value) {
        this.value = value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public void setLeftChildren(TreeNode leftChildren) {
        this.leftChildren = leftChildren;
    }

    public void setRightChildren(TreeNode rightChildren) {
        this.rightChildren = rightChildren;
    }

    public String getValue() {
        return value;
    }

    public TreeNode getLeftChildren() {
        return leftChildren;
    }

    public TreeNode getRightChildren() {
        return rightChildren;
    }
}

3、深度优先（DFS）

3.1、前序遍历

思路：先根节点->左子树->右子树；

二叉树如下图：

public class TreeSearch {
	
    public TreeNode getTargetTree() {
        // 叶子节点
        TreeNode G = new TreeNode("G");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E", G, null);
        TreeNode B = new TreeNode("B", D, E);
        TreeNode H = new TreeNode("H");
        TreeNode I = new TreeNode("I");
        TreeNode F = new TreeNode("F", H, I);
        TreeNode C = new TreeNode("C", null, F);
        // 构造根节点
        TreeNode root = new TreeNode("A", B, C);
        return root;
    }

    /**
     * 前序遍历 先根节点->左子树->右子树；
     */
    public void preOrderVisitTreeNode(TreeNode node) {
        if (null != node) {

            System.out.print(node.value);

            if (null != node.getLeftChildren()) {
                preOrderVisitTreeNode(node.getLeftChildren());
            }
            if (null != node.getRightChildren()) {
                preOrderVisitTreeNode(node.getRightChildren());
            }
        }
    }


    public static void main(String[] args) {

        TreeTest treeSearch = new TreeTest();
        TreeNode tree = treeSearch.getTargetTree();

        System.out.print("前序遍历:");
        treeSearch.preOrderVisitTreeNode(tree);
        System.out.println("");	
	}
}

运行结果：

先序遍历:ABDEGCFHI

3.2、中序遍历

思路：先左子树->根节点->右子树；

    /**
     *  中序遍历 先左子树->根节点->右子树；
     */
    public void inorderVisitTreeNode(TreeNode node) {
        if (null != node) {
            if (null != node.getLeftChildren()) {
                inorderVisitTreeNode(node.getLeftChildren());
            }

            System.out.print(node.value);

            if (null != node.getRightChildren()) {
                inorderVisitTreeNode(node.getRightChildren());
            }
        }
    }

    public static void main(String[] args) {
        TreeTest treeSearch = new TreeTest();
        TreeNode tree = treeSearch.getTargetTree();

        System.out.print("中序遍历:");
        treeSearch.inorderVisitTreeNode(tree);
        System.out.println("");
    }

运行结果：

中序遍历:DBGEACHFI

• 1

3.3、后序遍历

思路：先左子树->右子树->根节点；

    /**
     *  后序遍历 先左子树->右子树->根节点；
     */
    public void postOrderVisitTreeNode(TreeNode node) {
        if (null != node) {
            if (null != node.getLeftChildren()) {
                postOrderVisitTreeNode(node.getLeftChildren());
            }
            if (null != node.getRightChildren()) {
                postOrderVisitTreeNode(node.getRightChildren());
            }

            System.out.print(node.value);
        }
    }

    public static void main(String[] args) {
       TreeTest treeSearch = new TreeTest();
       TreeNode tree= treeSearch.getTargetTree();
       
        System.out.print("后序遍历:");
        treeSearch.postOrderVisitTreeNode(tree);
        System.out.println("");
    }

运行结果：

后序遍历:DGEBHIFCA

• 1

4、广度优先（BFS）

4.1、层次遍历

思路：先根节点，然后第二层，第三层，依次往下走，（同层节点从左往右输出）;

运行结果：

层序遍历:ABCDEFGHI

层序遍历二叉树，是非递归的队列实现的，就是利用队列的先进先出（FIFO）实现的。

5、完整代码：

public class TreeNode {

    String value = null; // 根节点
    TreeNode leftChildren = null; // 左子节点
    TreeNode rightChildren = null; // 右子节点

    public TreeNode(String value, TreeNode leftChildren, TreeNode rightChildren) {
        this.value = value;
        this.leftChildren = leftChildren;
        this.rightChildren = rightChildren;
    }

    public TreeNode(String value) {
        this.value = value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public void setLeftChildren(TreeNode leftChildren) {
        this.leftChildren = leftChildren;
    }

    public void setRightChildren(TreeNode rightChildren) {
        this.rightChildren = rightChildren;
    }

    public String getValue() {
        return value;
    }

    public TreeNode getLeftChildren() {
        return leftChildren;
    }

    public TreeNode getRightChildren() {
        return rightChildren;
    }
}

public class TreeTest {

    public TreeNode getTargetTree() {
        // 叶子节点
        TreeNode G = new TreeNode("G");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E", G, null);
        TreeNode B = new TreeNode("B", D, E);
        TreeNode H = new TreeNode("H");
        TreeNode I = new TreeNode("I");
        TreeNode F = new TreeNode("F", H, I);
        TreeNode C = new TreeNode("C", null, F);
        // 构造根节点
        TreeNode root = new TreeNode("A", B, C);
        return root;
    }

    /**
     * 前序遍历 先根节点->左子树->右子树；
     */
    public void preOrderVisitTreeNode(TreeNode node) {
        if (null != node) {

            System.out.print(node.value);

            if (null != node.getLeftChildren()) {
                preOrderVisitTreeNode(node.getLeftChildren());
            }
            if (null != node.getRightChildren()) {
                preOrderVisitTreeNode(node.getRightChildren());
            }
        }
    }

    /**
     *  中序遍历 先左子树->根节点->右子树；
     */
    public void inorderVisitTreeNode(TreeNode node) {
        if (null != node) {
            if (null != node.getLeftChildren()) {
                inorderVisitTreeNode(node.getLeftChildren());
            }

            System.out.print(node.value);

            if (null != node.getRightChildren()) {
                inorderVisitTreeNode(node.getRightChildren());
            }
        }
    }

    /**
     *  后序遍历 先左子树->右子树->根节点；
     */
    public void postOrderVisitTreeNode(TreeNode node) {
        if (null != node) {
            if (null != node.getLeftChildren()) {
                postOrderVisitTreeNode(node.getLeftChildren());
            }
            if (null != node.getRightChildren()) {
                postOrderVisitTreeNode(node.getRightChildren());
            }

            System.out.print(node.value);
        }
    }

    /**
     * 层次遍历
     */
    public void levelOrderVisitTreeNode(TreeNode node) {
        if (null != node) {
            LinkedList<TreeNode> list = new LinkedList<>();
            list.add(node);
            TreeNode currentNode;
            while (!list.isEmpty()) {

                currentNode = list.poll();

                System.out.print(currentNode.value);

                if (null != currentNode.getLeftChildren()) {
                    list.add(currentNode.getLeftChildren());
                }
                if (null != currentNode.getRightChildren()) {
                    list.add(currentNode.getRightChildren());
                }
            }
        }
    }

    public static void main(String[] args) {

        TreeTest treeSearch = new TreeTest();
        TreeNode tree = treeSearch.getTargetTree();

        System.out.print("前序遍历:");
        treeSearch.preOrderVisitTreeNode(tree);
        System.out.println("");

        System.out.print("中序遍历:");
        treeSearch.inorderVisitTreeNode(tree);
        System.out.println("");

        System.out.print("后序遍历:");
        treeSearch.postOrderVisitTreeNode(tree);
        System.out.println("");

        System.out.print("层次遍历:");
        treeSearch.levelOrderVisitTreeNode(tree);
    }
}

运行结果：

前序遍历:ABDEGCFHI
中序遍历:DBGEACHFI
后序遍历:DGEBHIFCA
层次遍历:ABCDEFGHI