二叉树的概念

什么是二叉树？

每个结点最多只有两个结点的树称为二叉树，如下图所示

如果二叉树的所有叶子结点都在最后一层并且结点的总数=2^n-1，其中n为层数，则称其为满二叉树

如果该二叉树的所有叶子结点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的也自己结点在右边连续，我们称为完全二叉树

二叉树的遍历

二叉树的遍历分为三种：

前序遍历：先输出父结点,再遍历左子树,再遍历右子树

中序遍历：先遍历左子树,再输出父结点,再遍历右子树

后序遍历：先遍历左子树,再遍历右子树,再输出父节点

小结：看父结点输出的顺序就能确定是前序还是中序后序,左子树的遍历一定再右子树前

代码实现

Node：模拟结点

/**
 * 模拟结点
 */
public class Node {
    private int id;
    private String name;
    /*左节点*/
    private Node left;
    /*右节点*/
    private Node right;

    /*构造方法*/
    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }
    /*前序遍历*/
    public void preDisplay(){
    	/*输出当前结点*/
        System.out.println(this);
        if (this.left != null) {
        	/*如果当前结点的左子节点不为空就递归前序遍历左子树*/
            this.left.preDisplay();
        }
        if (this.right != null) {
        	/*如果当前结点的右子节点不为空就递归前序遍历右子树*/
            this.right.preDisplay();
        }

    }
    /*中序遍历*/
    public void midDisplay(){
        if (this.left != null) {
            this.left.midDisplay();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midDisplay();
        }
    }
    /*后序遍历*/
    public void postDisplay(){
        if (this.left != null) {
            this.left.postDisplay();
        }
        if (this.right != null) {
            this.right.postDisplay();
        }
        System.out.println(this);
    }
	
	setter and getter方法
	
    @Override
    public String toString() {
        return "[" + "id=" + id + ", name='" + name  + ']';
    }
}

BinaryTree：模拟二叉树

public class BinaryTree {

    /*根结点*/
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }
    /*前序遍历*/
    public void preShow(){
        if (this.root != null) {
            this.root.preDisplay();
        }else{
            System.out.println("二叉树为空");
        }
    }
    /*中序遍历*/
    public void midShow(){
        if (this.root != null){
            this.root.midDisplay();
        }else{
            System.out.println("二叉树为空");
        }
    }
    /*后序遍历*/
    public void postShow(){
        if (this.root != null) {
            this.root.postDisplay();
        }else{
            System.out.println("二叉树为空");
        }
    }
}

BinaryTreeTest ：测试类

public class BinaryTreeTest {
    public static void main(String[] args) {
        /*手动创建结点*/
        Node node1 = new Node(1,"张三");
        Node node2 = new Node(2,"李四");
        Node node3 = new Node(3,"王五");
        Node node4 = new Node(4,"赵六");
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);

        /*创建二叉树*/
        BinaryTree tree = new BinaryTree();
        tree.setRoot(node1);

        System.out.println("前序遍历：");
        tree.preShow();//1,2,3,4

        System.out.println("中序遍历：");
        tree.midShow();//2,1,3,4

        System.out.println("后序遍历：");
        tree.postShow();//2,4,3,1

    }
}

结果输出

前序遍历：
[id=1, name='张三]
[id=2, name='李四]
[id=3, name='王五]
[id=4, name='赵六]
中序遍历：
[id=2, name='李四]
[id=1, name='张三]
[id=3, name='王五]
[id=4, name='赵六]
后序遍历：
[id=2, name='李四]
[id=4, name='赵六]
[id=3, name='王五]
[id=1, name='张三]

Process finished with exit code 0