Java实现二叉树~

一、创建一棵二叉树 

1、简单创建二叉树

//二叉树的实现
class Node{//创建节点
    public int val;
    public Node left;
    public Node right;
    public Node(int val){
        this.val=val;
    }
}

public class Binarytree {
    public Node root;//二叉树的根节点

    public Node createTree(){//简单方式创建二叉树
        Node A=new Node('A');
        Node B=new Node('B');
        Node C=new Node('C');
        Node D=new Node('D');
        Node E=new Node('E');
        Node F=new Node('F');
        Node G=new Node('G');
        Node H=new Node('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;//返回根
    }

测试二叉树是否创建成功： 

二、二叉树的前、中、后序遍历

1、二叉树的前序遍历

    //没有返回值的二叉树的前序遍历(根->左->右)
    void preOrder(Node root){//递归
        if(root==null){//递归结束条件：当没有节点的时候返回
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }



    //有返回值的二叉树的前序遍历
    //(法一：遍历思路，一个节点一个节点去遍历)
    List list=new ArrayList<>();//只创建一个list，遍历时只往这一个list里面添加
    public List preOrder1(Node root){
        if(root==null){
            return list;
        }
        list.add(root.val);//将根的值添加到list
        preOrder1(root.left);
        preOrder1(root.right);
        return list;
    }



    //（法二：子问题思路，拆分为根，根的左，根的右）
    public List preOrder2(Node root){
        List list=new ArrayList<>();//每次递归都创建一个list
        if(root==null){
            return list;
        }
        list.add(root.val);
        List leftTree=preOrder2(root.left);
        list.addAll(leftTree);//将这次递归的左树都放在list中，方便下次递归创建一个新的list后再将刚刚的左树放入
        List rightTree=preOrder2(root.right);
        list.addAll(rightTree);
        return list;

    }

2、二叉树的中序遍历

     //没有返回值的二叉树的中序遍历(左->根->右)
    void inOrder(Node root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }



    //有返回值的二叉树的中序遍历(法一：遍历思路)
    List list1=new ArrayList<>();
    public List inOrder1(Node root){
        if(root==null){
            return list1;
        }
        inOrder1(root.left);
        list1.add(root.val);
        inOrder1(root.right);
        return list1;
    }



    //有返回值的二叉树的中序遍历(法二：子问题思路)
    public List inOrder2(Node root){
        List list=new ArrayList<>();
        if(root==null){
            return list;
        }
        List leftTree=inOrder2(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List rightTree=inOrder2(root.right);
        list.addAll(rightTree);
        return list;
    }

3、二叉树的后序遍历

//没有返回值的二叉树的后序遍历(左->右->根)
    void postOrder(Node root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        inOrder(root.right);
        System.out.print(root.val+" ");
    }



    //有返回值的二叉树的后序遍历(法一：遍历思路)
    List list2=new ArrayList<>();
    public List preOrder1(Node root){
        if(root==null){
            return list2;
        }
        preOrder1(root.left);
        preOrder1(root.right);
        list2.add(root.val);
        return list2;
    }



    //有返回值的二叉树的后序遍历(法二：子问题思路)
    public List preOrder2(Node root){
        List list=new ArrayList<>();
        if(root==null){
            return list;
        }
        List leftTree=preOrder2(root.left);
        list.addAll(leftTree);
        List rightTree=preOrder2(root.right);
        list.addAll(rightTree);
        list.add(root.val);
        return list;
    }