数据结构 二叉树（B树）

BTree

特征：

1.一个节点最多只有两个子节点，其中左子节点的关键字小于这个节点，右子节点的关键字大于等于该节点。

2.执行查找，插入，删除的时间复杂度都是：O(logN)。

3.遍历有中序，前序，后序。前，中和后只是在递归的时候先输出左子，自己或右子的顺序。可以通过中排序，按左子，自己，右子的顺序就是升序，反之则是降序。

4.最大值是树的右边底层叶子；最小值是左边底层叶子。

 

JAVA代码实现：

 

 

package org.acooly.datastructure.btree;

import java.util.Random;

/**
 * 特征：一个节点的左子节点的关键字小于这个节点，右子节点的关键字大于等于该节点。
 *
 * @author zhangpu
 *
 */
public class BinaryTree {

    /** 根节点 */
    private Node root;

    /**
     * 查找
     *
     * @param key
     * @return
     */
    public Node find(int key) {
        if (root == null) {
            return null;
        }
        Node current = root;
        while (current.getKey() != key) {
            if (key < current.getKey()) {
                // 小于本节点在左边
                current = current.getLeftNode();
            } else {
                // 大于等于本节点在右边
                current = current.getRightNode();
            }
            if (current == null) {
                // 搜索到最后叶子为空，表示没有找到
                return null;
            }
        }
        return current;
    }

    public Node getParent(int key) {
        if (root == null) {
            return null;
        }
        Node current = root;
        Node parent = root;
        while (current.getKey() != key) {
            if (key < current.getKey()) {
                // 小于本节点在左边
                parent = current;
                current = current.getLeftNode();
            } else {
                // 大于等于本节点在右边
                parent = current;
                current = current.getRightNode();
            }
            if (current == null) {
                // 搜索到最后叶子为空，表示没有找到
                return null;
            }
        }
        return parent;
    }

    /**
     * 插入
     *
     * @param key
     * @param value
     */
    public void insert(int key, Object value) {
        Node node = new Node(key, value);
        if (root == null) {
            root = node;
            return;
        }
        Node current = root;
        while (true) {
            if (key < current.getKey()) {
                if (current.getLeftNode() == null) {
                    current.setLeftNode(node);
                    return;
                } else {
                    current = current.getLeftNode();
                }
            } else {
                if (current.getRightNode() == null) {
                    current.setRightNode(node);
                    return;
                } else {
                    current = current.getRightNode();
                }
            }
        }

    }

    /**
     * 中遍历(升序)
     *
     * @param startNode
     */
    public void inOrderAsc(Node startNode) {

        if (startNode != null) {
            inOrderAsc(startNode.getLeftNode());
            System.out.println(startNode);
            inOrderAsc(startNode.getRightNode());
        }

    }

    /**
     * 中遍历(降序)
     *
     * @param startNode
     */
    public void inOrderDesc(Node startNode) {
        if (startNode != null) {
            inOrderDesc(startNode.getRightNode());
            System.out.println(startNode);
            inOrderDesc(startNode.getLeftNode());
        }

    }

    /**
     * 最大值 算法：树中最底层的右子叶
     *
     * @return
     */
    public Node getMax() {
        Node current = root;
        while (current.getRightNode() != null) {
            current = current.getRightNode();
        }
        return current;
    }

    /**
     * 算法：树中最底层的左子叶
     *
     * @return
     */
    public Node getMin() {
        return getMin(root);
    }

    /**
     * 指定节点的最小节点，如果指定节点为root,则是树的最小节点
     *
     * @param localRoot
     * @return
     */
    private Node getMin(Node localRoot) {
        Node current = localRoot;
        while (current.getLeftNode() != null) {
            current = current.getLeftNode();
        }
        return current;
    }

    /**
     * 删除节点存在3中情况 <li>目标节点是叶子:直接删除,置为null <li>
     * 目标节点只有一个子节点:如果目标节点是在父节点的左边，直接使用子节点作为父节点的左子，反正则为右子。 <li>
     * 目标节点有两个子节点:找到后继节点，作为目标节点父节点的对应子节点。（后继：目标节点子节点中大于目标节点最小的个。路径：目标节点右子的最小节点。）
     *
     * @param key
     */
    public void delete(int key) {

        Node target = find(key);
        if (target == null) {
            return;
        }

        boolean leftExsit = (target.getLeftNode() != null ? true : false);
        boolean rightExsit = (target.getRightNode() != null ? true : false);
        // 第一种情况，目标是叶子，直接设置为null
        if (!leftExsit && !rightExsit) {
            target = null;
            return;
        }

        // 获得目标的父节点
        Node parent = getParent(key);
        Node child = null;
        if (leftExsit != rightExsit) {
            // 第二种情况：只有一个子
            child = (leftExsit ? target.getLeftNode() : target.getRightNode());
        } else {
            // 第三种情况：有两个子
            Node rightChild = target.getRightNode();
            child = getMin(rightChild);
            getParent(child.getKey()).setLeftNode(null);
            child.setRightNode(rightChild);
        }

        if (parent == null) {
            root = child;
            target = null;
            return;
        }

        if (parent.getLeftNode() != null && target.getKey() < parent.getLeftNode().getKey()) {
            // 目标是父的左子
            parent.setLeftNode(child);
        } else {
            // 目标是父的右子
            parent.setRightNode(child);
        }
        target = null;
    }

    public Node getRoot() {
        return root;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        Random random = new Random();
        // INSERT
        for (int i = 1; i <= 10; i++) {
            int key = random.nextInt(100);
            tree.insert(key, "value" + key);
        }
        int key = 0;
        tree.insert(key, "value" + key);
        System.out.println("TARGET key: " + key);
        // FIND
        System.out.println("FIND: " + tree.find(key));
        // GETPARENT
        System.out.println("PARENT: " + tree.getParent(key));
        // MIX
        System.out.println("MAX: " + tree.getMax());
        // MIN
        System.out.println("MIN: " + tree.getMin());
        tree.delete(key);
        System.out.println();
        System.out.println("中遍历(升序)：");
        tree.inOrderAsc(tree.getRoot());
        System.out.println("中遍历(降序)：");
        tree.inOrderDesc(tree.getRoot());
    }

}

   节点类：

 

package org.acooly.datastructure.btree;

/**
 * BTree 节点
 *
 * @author zhangpu
 *
 */
public class Node {

    /** 节点KEY */
    private int key;
    private Object value;
    /** 左子节点 */
    private Node leftNode;
    /** 右子节点 */
    private Node rightNode;

    public Node() {
        super();
    }

    public Node(int key, Object value) {
        super();
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return String.valueOf(key) + "=" + value;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Node){
            Node n = (Node)obj;
            if(n.getKey() != getKey()){
                return false;
            }
        }else{
            return false;
        }
        return true;
    }

}