二叉树遍历等基本操作(Java实现)

前中后序遍历递归实现+层序遍历：

树的结点类代码： 

public class TreeNode<Value extends Comparable<? super Value>> {
    private Value value;
    private TreeNode left;
    private TreeNode right;

    public Value getValue() {
        return value;
    }

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

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

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

接下来对这颗树进行遍历：

 

遍历类代码：

public class Treetraversal {
    /**
     * 前序遍历，先根遍历
     *
     * @param node 树的根
     */
    public static void preOrder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.getValue() + "\t");
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    /**
     * 中序遍历，中根遍历
     *
     * @param node 树的根
     */
    public static void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.getLeft());
        System.out.print(node.getValue() + "\t");
        inOrder(node.getRight());
    }

    /**
     * 后序遍历，后根遍历
     *
     * @param node 树的根
     */
    public static void postOrder(TreeNode node) {
        if (node == null) return;
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.print(node.getValue() + "\t");
    }

    /**
     * 层序遍历，层次遍历
     *
     * @param node 树的根
     */
    public static void levelOrder(TreeNode node) {
        java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.pop();
            System.out.print(cur.getValue() + "\t");
            if (cur.getLeft() != null) queue.add(cur.getLeft());
            if (cur.getRight() != null) queue.add(cur.getRight());
        }
    }

    public static void main(String[] args) {
        //创建一颗树，一个样例
        TreeNode<Character> 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'));

        preOrder(root);//A   B   D   E   G   C   F   
        System.out.println();
        inOrder(root);//D   B   G   E   A   C   F   
        System.out.println();
        postOrder(root);//D   G   E   B   F   C   A
        System.out.println();
        levelOrder(root);//A   B   C   D   E   F   G
    }
} 

求树的深度

树结点类的代码和上面一样。测试用的树也和上面一样。

求二叉树深度的代码(递归)：

 

public class TreeDepth {
    public static int treeDepth(TreeNode node) {
        if (node == null) return 0;
        return Math.max(treeDepth(node.getLeft()), treeDepth(node.getRight())) + 1;
    }

    public static void main(String[] args) {
        //创建一颗树，一个样例
        TreeNode<Character> 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'));

        int depth = treeDepth(root);
        System.out.println(depth);//4
    }
}　　

求二叉树叶子节点个数：

树结点类的代码和上面一样。测试用的树也和上面一样。

求二叉树叶子结点的代码(递归)：

public class LeafCounter {
    public static int leafCount(TreeNode node) {
        if (node == null) return 0;
        if (node.getLeft() == null && node.getRight() == null) return 1;
        return leafCount(node.getLeft()) + leafCount(node.getRight());
    }

    public static void main(String[] args) {
        //创建一颗树，一个样例
        TreeNode<Character> 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'));

        int count = leafCount(root);
        System.out.println(count);//3
    }
}