二叉查找树

二叉查找树或者是空树，或者是满足以下性质的二叉树：
1、若它的左子树非空，则左子树上所有的节点值均小于根节点值
2、若它的右子树非空，则右子树上所有的节点值均大于或等于根节点值
3、左右子树本身又各是一颗二叉查找树

二叉树节点类

class Node{
    private int key;
    private Node left;
    private Node right;

    public Node(int key) {
        this.key = key;
    }

    public Node() {
    }

    public int getKey() {
        return key;
    }

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

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

中序遍历二叉树

public static void LoopNode(Node root){
        if (root!=null){
            LoopNode(root.getLeft());
            System.out.print(root.getKey()+"  ");
            LoopNode(root.getRight());
        }
    }

二叉树中插入一个节点
不考虑空树的情况，具体操作如下：
1、若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中。
2、若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中。
3、若待插入结点的值等于根结点的值，则插入结点失败。

public static void AddNode(Node root,int key){
        if (key< root.getKey()){
            if (root.getLeft()==null){
                Node temp = new Node(key);
                root.setLeft(temp);
                System.out.println(key+"插入成功");
            }else{
                AddNode(root.getLeft(),key);
            }
        }else if (key> root.getKey()){
            if (root.getRight()==null){
                Node temp = new Node(key);
                root.setRight(temp);
                System.out.println(key+"插入成功");
            }else {
                AddNode(root.getRight(),key);
            }
        }else{
            System.out.println(key+"插入失败");
        }
    }

注意：此处没有考虑根节点为空的情况！！！
删除二叉树的一个节点
删除时分三种情况：
1、待删除节点的左子树为空：当我们在二叉搜索树当中找到该结点后，只需先让其父结点指向该结点的右孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍保持二叉搜索树的特性。
2、待删除节点的右子树为空：当我们在二叉搜索树当中找到该结点后，只需先让其父结点指向该结点的左孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍保持二叉搜索树的特性。
3、待删除节点的左右子树均不为空：当我们在二叉搜索树当中找到该结点后，可以使用替换法进行删除。可以将让待删除结点左子树当中值最大的结点，或是待删除结点右子树当中值最小的结点代替待删除结点被删除（下面都以后者为例），也就是把左子树的最大值或右子树的最小值赋给待删除节点，进行删除操作后仍保持二叉搜索树的特性，然后删除代替删除的节点。而代替待删除结点，必然左右子树当中至少有一个为空树，因此删除该结点的方法与前面说到的情况一和情况二的方法相同。

public static void DelNode(Node root,int key){
        Node temp = root;
        Node FatherNode = null;
        while (temp!=null){
            if (temp.getKey()key){
                FatherNode = temp;
                temp=temp.getRight();
            }else {
                if (temp.getLeft()==null){
                    if (FatherNode==null){ //待删除的节点是根节点
                        root = root.getRight();
                    }else {
                        //如果待删除节点是父节点的左子树
                        if (FatherNode.getLeft()==temp){
                            FatherNode.setLeft(temp.getRight());
                        }else {
                            FatherNode.setRight(temp.getRight());
                        }
                    }
                }else if (temp.getRight()==null){
                    if (FatherNode==null){
                        root=root.getLeft();
                    }else {
                        //如果待删除节点是父节点的左子树
                        if (FatherNode.getLeft()==temp){
                            FatherNode.setLeft(temp.getRight());
                        }else {
                            FatherNode.setRight(temp.getRight());
                        }
                    }
                }else {
//                    左右子树都不为空，使用右子树的最小节点代替待删除节点
                    Node ChildMin = temp.getRight();
                    Node ChildMinFather = temp;
                    while (ChildMin.getLeft()!=null){
                        ChildMinFather = ChildMin;
                        ChildMin = ChildMin.getLeft();
                    }
//                    此时找到的右子树的最小值的左子树为空
                    temp.setKey(ChildMin.getKey());
                    if (ChildMinFather.getLeft()==ChildMin){
                        ChildMinFather.setLeft(ChildMin.getRight());
                    }else {
//                        删除节点为根节点的情况
                        ChildMinFather.setRight(ChildMin.getRight());
                    }
                }
            }
        }
    }

递归查找二叉树

public static Node FindNode(Node root,int key){
        if (root!=null){
            if (root.getKey()==key){
                return root;
            }else if (key< root.getKey()){
                return FindNode(root.getLeft(),key);
            }else {
                return FindNode(root.getRight(),key);
            }
        }else {
            return null;
        }
    }

另外二叉树还有一个kv模型，比如想要实现根据英文来查找对应的中文，可以在节点类中存储英文以及对应的中文，在进行查找的时候使用java的compareTo方法来判断两个单词的大小，从而选择查找左子树还是右子树，就能实现字典的功能了。