Java实现二叉树

用Java实现的时候一般对照着C的代码来写，写的时候有一些问题。

1. 根节点信息丢失

在运行CreateTree函数无误，但是在进行各种排列时只能显示根节点，左节点和右节点的值并没有被保存，通过排查发现函数中在进行递归插入左右节点的时候直接使用了node.leftnode,问题就出现在这里，这个node。leftnode是TreeNode类型，并没有初始化需要先new一下。

2. 各种排序会出现0的状况

其实这个问题就是上面的方法产生的，在插入左右结点之前就创建了左右结点，以后有时间优化一下，这里的解决方案有屏蔽结点值为0，运行结果就是下面的了，我觉得写个函数删除一下应该也可以

代码：

package Tree;
import java.util.Scanner;
public class Main{
    static class TreeNode{
        TreeNode leftnode;
        TreeNode rightNode;
        int data;
        public TreeNode(){
        }
    }
    public static void main(String[] args) {
        System.out.print("请输入根节点：");
        TreeNode root=new TreeNode();
        CreateTree(root);
        System.out.print("前：");
        PreOrderTree(root);
        System.out.print("\n中：");
        InOrderTree(root);
        System.out.print("\n后：");
        PostOrderTree(root);
        System.out.println("\nMaxDeep:"+MaxDeep(root));
    }
    /**
     * LeetCode(104),二叉树最大深度
     * @param root
     * @return
     */
    private static int MaxDeep(TreeNode root){
        if (root==null||root.data==0){
            return 0;
        }else{
            int maxleft = MaxDeep(root.leftnode);
            int maxright = MaxDeep(root.rightNode);
            if (maxleft>maxright){
                return maxleft+1;
            }else{
                return maxright+1;
            }
        }
    }
    /**
     * 初始化二叉树
     * @param node
     */
    public static void CreateTree(TreeNode node){
        Scanner input = new Scanner(System.in);
        int data = input.nextInt();
        if(data<=0){
            node = null;
            return;
        }else{
            //node = new TreeNode();
            node.data = data;
            System.out.println("请输入"+data+"的左节点");
            node.leftnode = new TreeNode();
            CreateTree(node.leftnode);
            System.out.println("请输入"+data+"的右节点");
            node.rightNode = new TreeNode();
            CreateTree(node.rightNode);
        }
    }
    /**
     * 中序排列
     * @param root
     */
    private static void InOrderTree(TreeNode root) {
        if (root==null||root.data==0){
            return;
        }
        InOrderTree(root.leftnode);
        System.out.print(root.data+" ");
        InOrderTree(root.rightNode);
    }

    /**
     * 后序排列
     * @param root
     */
    public static void PostOrderTree(TreeNode root){
        if(root==null||root.data==0){
            return;
        }
        PostOrderTree(root.leftnode);
        PostOrderTree(root.rightNode);
        System.out.print(root.data+" ");
    }

    /**
     * 前序排列
     * @param root
     */
    public static void PreOrderTree(TreeNode root){
        if(root==null||root.data==0){
            return;
        }
        System.out.print(root.data+" ");
        PreOrderTree(root.leftnode);
        PreOrderTree(root.rightNode);
    }
}

运行结果：

请输入根节点：3
请输入3的左节点
2
请输入2的左节点
2
请输入2的左节点
0
请输入2的右节点
0
请输入2的右节点
0
请输入3的右节点
8
请输入8的左节点
6
请输入6的左节点
5
请输入5的左节点
4
请输入4的左节点
0
请输入4的右节点
0
请输入5的右节点
0
请输入6的右节点
0
请输入8的右节点
0
前：3 2 2 8 6 5 4 
中：2 2 3 4 5 6 8 
后：2 2 4 5 6 8 3 
MaxDeep:5