数据结构——二叉树（Java 实现）_基于组合模式，使用 java 语言中实现一个二叉树的数据结构。

为什么使用二叉树？

1.在有序数据中插入数据项太慢；

2.在链表中查找太慢；

树既能向链表那样快速的插入和删除，又能像有序数组那样快速查找。

树的术语

路径：设想一下顺着连接节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。

根：树顶端的节点称为“根”。一棵树有且仅有一个根。

父节点，子节点。

叶节点：没有子节点的节点。

子树。

访问，遍历，层，关键字，二叉树，二叉搜索树。

二叉树和二叉搜索树区别联系？

二叉树指这样的树结构，它的每个结点的孩子数目最多为2个；二叉搜索树是一种二叉树，但是它有附加的一些约束条件，这些约束条件必须对每个结点都成立：

• 结点node的左子树所有结点的值都小于node的值。
• 结点node的右子树所有结点的值都大于node的值。
• 结点node的左右子树同样都必须是二叉搜索树。

/**
 * Created by Zhans on 2018/9/4.
 * TreeApp
 * 二叉搜索树
 */
 
/**
 * 节点类
 */
class Node {
    public int iData;// 节点中的整数型数据(key)
    public double dData;//节点中的浮点型数据
    public Node leftChild;//该节点的左子节点
    public Node rightChild;//该节点的右子节点
 
    public void displayNode() {
        System.out.print('{');
        System.out.print(iData);
        System.out.print(", ");
        System.out.print(dData);
        System.out.print('}');
    }
 
}
 
 
/**
 * 树本身的类，由这个类实例化的对象含有所有的节点。它只有一个数据字段，一个表示根的Node变量
 */
class Tree {
    private Node root;
 
    public Node find(int key) {//根据关键字key查找节点,假设不是空树
        Node current = root;
 
        while (current.iData != key) {
            if (current.iData < key)
                current = current.leftChild;
            else
                current = current.rightChild;
            if (current == null)
                return null;
        }
        return current;
    }
 
    public void insert(int id, double dd) {
        Node newNode = new Node();
        newNode.iData = id;
        newNode.dData = dd;
 
        if (root == null) //没有根节点
            root = newNode;
        else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (id < current.iData) {
                    current = parent.leftChild;
                    if (current == null) {
                        parent.leftChild = newNode;
                        return;
                    }
                } else {
                    current = parent.rightChild;
                    if (current == null) {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }
 
    public boolean delete(int key) {//删除关键词key所在的节点
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;
 
        while (current.iData != key) {//首先找到要删除的节点
            parent = current;
            if (key < current.iData) {
                isLeftChild = true;
                current = current.leftChild;
            } else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null)
                return false;
        }
 
        if (current.leftChild == null && current.rightChild == null) {//要删除的节点为叶节点（没有子节点的节点）
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
        } else if (current.rightChild == null) {//要删除的节点没有右子节点
            if (current == root)
                root = current.leftChild;
            else if (isLeftChild)
                parent.leftChild = current.leftChild;
            else
                parent.rightChild = current.leftChild;
        } else if (current.leftChild == null) {//要删除的节点没有左子节点
            if (current == root)
                root = current.rightChild;
            else if (isLeftChild)
                parent.leftChild = current.rightChild;
            else
                parent.rightChild = current.rightChild;
        } else {//要删除的节点有两个子节点,用该节点的后继节点代替此节点（后继节点：比该节点关键字值大的节点集合中最小的一个节点）
            Node successor = getSuccessor(current);
 
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.leftChild = successor;
            else
                parent.rightChild = successor;
 
            successor.leftChild = current.leftChild;
        }
        return true;
    }
 
    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rightChild;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        if (successor != delNode.rightChild) {
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }
 
    /**
     * 中序遍历：
     * 1.调用自身访该节点的左子树
     * 2.访问节点
     * 3.调用自身访问该节点的右子树
     */
    private void inorderTraversal(Node localRoot) {
        if (localRoot != null) {
            inorderTraversal(localRoot.leftChild);
            System.out.print(localRoot.iData + " ");
            inorderTraversal(localRoot.rightChild);
        }
    }
 
    /**
     * 前序遍历：
     * 1.访问节点
     * 2.调用自身访该节点的左子树
     * 3.调用自身访问该节点的右子树
     */
    private void preorderTraversal(Node localRoot) {
        if (localRoot != null) {
            System.out.print(localRoot.iData + " ");
            preorderTraversal(localRoot.leftChild);
            preorderTraversal(localRoot.rightChild);
        }
    }
 
    /**
     * 后序遍历：
     * 1.调用自身访该节点的左子树
     * 2.调用自身访问该节点的右子树
     * 3.访问节点
     */
    private void postorderTraversal(Node localRoot) {
        if (localRoot != null) {
            postorderTraversal(localRoot.leftChild);
            postorderTraversal(localRoot.rightChild);
            System.out.print(localRoot.iData + " ");
        }
    }
 
}
 
 
/**
 * 操作数的类
 */
public class TreeApp {
}