java数据结构和算法------二叉树基本操作

package iYou.neugle.tree;

import java.util.ArrayList;
import java.util.List;

public class Binary_Tree<T> {
    private Tree tree = new Tree();

    class Tree {
        public T data;
        public Tree left;
        public Tree right;
    }

    public enum Direction {
        left, right
    }

    // 生成根节点
    public void CreateRoot(T data) {
        this.tree.data = data;
    }

    // 插入节点到指定位置
    public boolean Insert(T parentData, T data, Direction direction) {
        if (this.TreeIsEmpty()) {
            System.out.println("树暂无节点，请先创建树");
            return false;
        }
        return this.InsertNode(this.tree, parentData, data, direction);
    }

    private boolean InsertNode(Tree TreeNode, T parentData, T data,
            Direction direction) {
        if (TreeNode == null) {
            return false;
        }
        if (TreeNode.data.equals(parentData)) {
            Tree t = new Tree();
            t.data = data;
            if (direction == Direction.left) {
                if (TreeNode.left == null) {
                    TreeNode.left = t;
                    return true;
                } else {
                    System.out.println("该节点的左节点不为空!");
                }
            } else {
                if (TreeNode.right == null) {
                    TreeNode.right = t;
                    return true;
                } else {
                    System.out.println("该节点的右节点不为空!");
                }
            }
            return false;
        }

        boolean b = InsertNode(TreeNode.left, parentData, data, direction);

        if (!b) {
            return InsertNode(TreeNode.right, parentData, data, direction);
        } else {
            return b;
        }

    }

    // 获取二叉树深度
    public int Deep() {
        return this.TreeDeep(this.tree);
    }

    private int TreeDeep(Tree tree) {
        int leftLen = 0;
        int rightLen = 0;
        if (tree == null) {
            return 0;
        }
        leftLen = this.TreeDeep(tree.left);
        rightLen = this.TreeDeep(tree.right);
        if (leftLen > rightLen) {
            return leftLen + 1;
        } else {
            return rightLen + 1;
        }
    }

    // 判断二叉树是否为空
    public boolean TreeIsEmpty() {
        if (this.tree.data != null) {
            return false;
        }
        return true;
    }

    // 根据值查找节点
    public Tree Query(T data) {
        return QueryTreeByValue(this.tree, data);
    }

    private Tree QueryTreeByValue(Tree tree, T data) {
        if (tree == null) {
            return null;
        }
        if (tree.data.equals(data)) {
            System.out.println("----------");
            System.out.println("查找到该节点，节点左子树为:"
                    + (tree.left == null ? "无" : tree.left.data));
            System.out.println("查找到该节点，节点右子树为:"
                    + (tree.right == null ? "无" : tree.right.data));
            System.out.println("----------");
            return tree;
        }
        Tree t = QueryTreeByValue(tree.left, data);
        if (t == null) {
            return QueryTreeByValue(tree.right, data);
        } else {
            return t;
        }
    }

    // 清空二叉树
    public void ClearTree() {
        this.tree = null;
    }

    // 先序遍历
    public void DLR() {
        this.Tree_DLR(this.tree);
    }

    private void Tree_DLR(Tree tree) {
        if (tree == null) {
            return;
        }
        System.out.println(tree.data);
        this.Tree_DLR(tree.left);
        this.Tree_DLR(tree.right);
    }

    // 中序遍历
    public void LDR() {
        this.Tree_LDR(this.tree);
    }

    private void Tree_LDR(Tree tree) {
        if (tree == null) {
            return;
        }
        this.Tree_LDR(tree.left);
        System.out.println(tree.data);
        this.Tree_LDR(tree.right);
    }

    // 后序遍历
    public void LRD() {
        this.Tree_LRD(this.tree);
    }

    private void Tree_LRD(Tree tree) {
        if (tree == null) {
            return;
        }
        this.Tree_LRD(tree.left);
        this.Tree_LRD(tree.right);
        System.out.println(tree.data);
    }

    // 层次遍历
    public void Level() {
        List<Tree> list = new ArrayList<Tree>();
        list.add(this.tree);
        while (!list.isEmpty()) {
            Tree left = list.get(0).left;
            Tree right = list.get(0).right;
            if (left != null) {
                list.add(left);
            }
            if (right != null) {
                list.add(right);
            }
            System.out.println(list.get(0).data);
            list.remove(0);
        }
    }
}