【数据结构（五）】树----01-ADT二叉树

1. 优点
   1. 二叉树的平均深度是O（log N），一般不用担心栈空间被用尽；
   2. 要求所有的项都可以进行排序，所以需要实现一个Comparable接口；
   3. 使用的是递归的方式进行数据的查找/删除/增加/修改；
2. 缺点
   1. 如果数据量过于庞大，会导致二叉树的深度过深，导致效率会急剧低下；
   2. 如果使用删除操作会使树节点位置进行改变，操作复杂（解决是使用删除标识符）；

代码如下：

package com.xiao.java_base.btree;


public class BinarySearchTree> {

    private static class BinaryTreeNode {
        T element; // current element information
        BinaryTreeNode leftNode; // left node
        BinaryTreeNode rightNode; // right node
        int flag; // logic deleted; 

        public BinaryTreeNode(T element) {
            this(element, null, null);
        }

        public BinaryTreeNode(T element, BinaryTreeNode leftNode, BinaryTreeNode rightNode) {
            this.element = element;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.flag = 0;
        }

        @Override
        public String toString() {
            return "BinaryTreeNode{" +
                    "element=" + element +
                    ", leftNode=" + leftNode +
                    ", rightNode=" + rightNode +
                    ", flag=" + flag +
                    '}';
        }
    }

    private BinaryTreeNode binaryTreeNode;


    public boolean isEmpty(BinaryTreeNode root) {
        return root == null;
    }

    public T min(BinaryTreeNode root) {
        if (!isEmpty(root))
            return null;
        if (root.leftNode == null)
            return root.element;
        else
            return min(root.leftNode);
    }

    
    public BinaryTreeNode insert(T t, BinaryTreeNode root) {
        if (root == null)
            return new BinaryTreeNode(t, null, null);
        int i = t.compareTo(root.element);
        if (i < 0)
            root.leftNode = insert(t, root.leftNode);
        else if (i > 0)
            root.rightNode = insert(t, root.rightNode);
        return root;
    }

    public boolean contains(T t, BinaryTreeNode root) {
        if (root == null)
            return false;
        int i = t.compareTo(root.element);
        if (i < 0)
            return contains(t, root.leftNode);
        else if (i > 0)
            return contains(t, root.rightNode);
        else
            return true;
    }

    
    public BinaryTreeNode remove(T t, BinaryTreeNode root) {
        if (root == null)
            return null; // Item not found;do nothing;
        int compareResult = t.compareTo(root.element);

        if (compareResult < 0)
            root.leftNode = remove(t, root.leftNode);
        else if (compareResult > 0)
            root.rightNode = remove(t, root.rightNode);
        else if (root.leftNode != null && root.rightNode != null) {
            root.element = min(root.rightNode);
            root.rightNode = remove(root.element, root.rightNode);
        } else
            root = (root.leftNode != null) ? root.leftNode : root.rightNode;
        return root;
    }

    
    public BinaryTreeNode removeByLogicDeleted(T t, BinaryTreeNode root) {
        if (root == null)
            return null; // The same above；
        int compareResult = t.compareTo(root.element);
        if (compareResult < 0)
            root.leftNode = removeByLogicDeleted(t, root.leftNode);
        else if (compareResult > 0)
            root.rightNode = removeByLogicDeleted(t, root.rightNode);
        else
            root.flag = 1;
        return root;
    }

    public static void main(String[] args) {
        BinarySearchTree bTree = new BinarySearchTree<>();
        BinaryTreeNode root = new BinaryTreeNode(1, null, null);
        bTree.insert(11, root);
        bTree.insert(12, root);
        bTree.insert(14, root);
        bTree.insert(10, root);
        System.out.println(root);
        System.out.println("*** invoke remove a item from btree! ***");
        bTree.remove(14, root);
        System.out.println(root);
        System.out.println("*** invoke removeByLogicDeleted a item from btree! ***");
        bTree.removeByLogicDeleted(11, root);
        System.out.println(root);

    }
}

BinaryTreeNode{element=1, leftNode=null, rightNode=BinaryTreeNode{element=11, leftNode=BinaryTreeNode{element=10, leftNode=null, rightNode=null, flag=0}, rightNode=BinaryTreeNode{element=12, leftNode=null, rightNode=BinaryTreeNode{element=14, leftNode=null, rightNode=null, flag=0}, flag=0}, flag=0}, flag=0}

*** invoke remove a item from btree! ***
BinaryTreeNode{element=1, leftNode=null, rightNode=BinaryTreeNode{element=11, leftNode=BinaryTreeNode{element=10, leftNode=null, rightNode=null, flag=0}, rightNode=BinaryTreeNode{element=12, leftNode=null, rightNode=null, flag=0}, flag=0}, flag=0}

*** invoke removeByLogicDeleted a item from btree! ***
BinaryTreeNode{element=1, leftNode=null, rightNode=BinaryTreeNode{element=11, leftNode=BinaryTreeNode{element=10, leftNode=null, rightNode=null, flag=0}, rightNode=BinaryTreeNode{element=12, leftNode=null, rightNode=null, flag=0}, flag=1}, flag=0}

public boolean contains(T t, BinaryTreeNode root) {
    if (root == null)
        return false;
    int i = t.compareTo(root.element);
    if (i < 0)
        return contains(t, root.leftNode);
    else if (i > 0)
        return contains(t, root.rightNode);
    else
        return true;
}

public T min(BinaryTreeNode root) {
    if (!isEmpty(root))
        return null;
    if (root.leftNode == null)
        return root.element;
    else
        return min(root.leftNode);
}

public BinaryTreeNode insert(T t, BinaryTreeNode root) {
    if (root == null)
        return new BinaryTreeNode(t, null, null);
    int i = t.compareTo(root.element);
    if (i < 0)
        root.leftNode = insert(t, root.leftNode);
    else if (i > 0)
        root.rightNode = insert(t, root.rightNode);
    return root;
}

public BinaryTreeNode remove(T t, BinaryTreeNode root) {
    if (root == null)
        return null; // Item not found;do nothing;
    int compareResult = t.compareTo(root.element);

    if (compareResult < 0)
        root.leftNode = remove(t, root.leftNode);
    else if (compareResult > 0)
        root.rightNode = remove(t, root.rightNode);
    else if (root.leftNode != null && root.rightNode != null) {
        root.element = min(root.rightNode);
        root.rightNode = remove(root.element, root.rightNode);
    } else
        root = (root.leftNode != null) ? root.leftNode : root.rightNode;
    return root;
}

使用逻辑删除标识符进行表示

public BinaryTreeNode removeByLogicDeleted(T t, BinaryTreeNode root) {
    if (root == null)
        return null; // The same above；
    int compareResult = t.compareTo(root.element);
    if (compareResult < 0)
        root.leftNode = removeByLogicDeleted(t, root.leftNode);
    else if (compareResult > 0)
        root.rightNode = removeByLogicDeleted(t, root.rightNode);
    else
        root.flag = 1;
    return root;
}