[Java]java实现二叉树遍历

我们来用java构造一下下图中的二叉树，并实现该二叉树的前序、中序和后序遍历。

二叉树都是由节点组成的，所以我们首先要有个节点类。

TreeNode类代码：

public class TreeNode {
private int num;
private TreeNode leftChild = null;
private TreeNode rightChild = null;

public TreeNode(int num) {
this.num = num;
    }

public void printNode(){
        System.out.println(this.getNum());
    }

public int getNum() {
return num;
    }

public void setNum(int num) {
this.num = num;
    }


public void setLeftChild(TreeNode node) {
this.leftChild = node;

    }

public void setRightChild(TreeNode node) {
this.rightChild = node;

    }

public TreeNode getLeftChild() {
return leftChild;
    }

public TreeNode getRightChild() {
return rightChild;
    }
}

然后就可以构建二叉树了，每个二叉树的节点都有一个值，然后此节点又包含一个左子节点和一个右子节点。

BinaryTree类代码：

public class BinaryTree {
private TreeNode root=null; 

public void createBinaryTree(){
        root = new TreeNode(1);

        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(6);
        TreeNode node6 = new TreeNode(7);

        root.setLeftChild(node1);
        root.setRightChild(node2);
        node1.setLeftChild(node3);
        node1.setRightChild(node4);
        node2.setLeftChild(node5);
        node2.setRightChild(node6);
    }

// 前序遍历
public void preOrder(TreeNode subTree){
if(subTree != null){
            subTree.printNode();
            preOrder(subTree.getLeftChild());
            preOrder(subTree.getRightChild());
        }
    }

// 中序遍历
public void inOrder(TreeNode subTree){
if(subTree != null){
            inOrder(subTree.getLeftChild());
            subTree.printNode();
            inOrder(subTree.getRightChild());
        }
    }

// 后序遍历
public void postOrder(TreeNode subTree){
if(subTree != null){
            postOrder(subTree.getLeftChild());
            postOrder(subTree.getRightChild());
            subTree.printNode();
        }
    }

public TreeNode getRoot() {
return this.root;
    }
}

好了，可以再写个类测试一下遍历效果。

TestTree类代码：

public class TestTree {
public static void main(String[] args) {
        BinaryTree bTree = new BinaryTree();
        bTree.createBinaryTree();

// 前序遍历
        System.out.println("--------前序遍历----------start");
        bTree.preOrder(bTree.getRoot());
        System.out.println("--------前序遍历----------end");

// 中序遍历
        System.out.println("--------中序遍历----------start");
        bTree.inOrder(bTree.getRoot());
        System.out.println("--------中序遍历----------end");

// 后序遍历
        System.out.println("--------后序遍历----------start");
        bTree.postOrder(bTree.getRoot());
        System.out.println("--------后序遍历----------end");
    }
}

输出结果如下：

——–前序遍历———-start
1
2
4
5
3
6
7
——–前序遍历———-end
——–中序遍历———-start
4
2
5
1
6
3
7
——–中序遍历———-end
——–后序遍历———-start
4
5
2
6
7
3
1
——–后序遍历———-end