Java实现二叉树

1、首先，二叉树的节点结构如下所示

package code.Tree;

public class Node {
    public Node lChild;     //左孩子
    private T data;             //数据域
    public Node rChild;     //右孩子
    public Node()              //构造函数，创建一个空节点
    {
        data = null;
        lChild = null;
        rChild = null;
    }
    public Node(T x)               //重载构造函数，创建一个数据值为x的节点
    {
        data = x;
        lChild = null;
        rChild = null;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

2、接下来是二叉树的相关属性以及方法

package code.Tree;

public class BinaryTree {
    public final int maxNodes = 100;

    private Node root;
    //创建一棵空二叉树
    public BinaryTree(){
        this.root = new Node();
    }

    //创建一棵以数据元素x为根结点的二叉树
    public BinaryTree(T x){
        this.root = new Node(x);
    }

    
    public boolean insertLeft(T x, Node parent){
        if(parent == null){
            return false;
        }
        Node p = new Node<>(x);
        if (parent.lChild == null){
            parent.lChild = p;
        }else {
            p.lChild = parent.lChild;
            parent.lChild = p;
        }
        return true;
    }

    
    public boolean insertRight(T x, Node parent){
        if (parent == null){
            return false;
        }
        Node p = new Node<>(x);
        if (parent.rChild == null){
            parent.rChild = p;
        }else {
            p.rChild = parent.rChild;
            parent.rChild = p;
        }
        return true;
    }

    //删除在当前二叉树的parent结点中的左子树
    public boolean deleteLeft(Node parent){
        if (parent == null){
            return false;
        }else {
            parent.lChild = null;
            return true;
        }
    }

    //删除在当前二叉树的parent结点中的右子树
    public boolean deleteRight(Node parent){
        if (parent == null){
            return false;
        }else {
            parent.rChild = null;
            return true;
        }
    }

    //输出节点数据
    public void visit(Node node){
        System.out.println(node.getData());
    }

    //先序遍历二叉树
    public void preorder(Node node){
        if (node == null){
            return;
        }else {
            //DLR
            visit(node);
            preorder(node.lChild);
            preorder(node.rChild);
        }

    }

    //中序遍历二叉树
    public void inorder(Node node){
        if (node == null){
            return;
        }else {
            //LDR
            inorder(node.lChild);
            visit(node);
            inorder(node.rChild);
        }
    }

    //后序遍历二叉树
    public void postorder(Node node){
        if (node == null){
            return;
        }else {
            //LRD
            postorder(node.lChild);
            postorder(node.rChild);
            visit(node);
        }

    }

    //层次遍历二叉树
    public void levelOrder(){
        Node [] queue = new Node[this.maxNodes];
        int front,rear;
        front = -1;
        rear = 0;
        if (this.root == null){
            return;
        }
        rear++;
        queue[rear] = this.root;
        while (front != rear){
            front++;
            visit(queue[front]);
            if (queue[front].lChild != null){
                rear++;
                queue[rear] = queue[front].lChild;
            }
            if (queue[front].rChild != null){
                rear++;
                queue[rear] = queue[front].rChild;
            }
        }
    }

    

    //按某种方式遍历当前二叉树的全部结点
    public void traversal(int i){
        switch (i){
            case 0:
                preorder(this.root);
                break;
            case 1:
                inorder(this.root);
                break;
            case 2:
                postorder(this.root);
                break;
            default:
                levelOrder();
        }
    }

    //求当前二叉树的高度
    public int getHeight(Node parent){
        int lh,rh,max;
        if (parent != null){
            lh = getHeight(parent.lChild);
            rh = getHeight(parent.rChild);
            max = lh > rh ? lh : rh;
            return max + 1;
        }else {
            return 0;
        }
    }


}