（JAVA）开始熟悉 “二叉树” 的数据结构

package com.renexdemo.tree;

// 二叉查找树
public class BinaryTree<Key extends Comparable<Key> ,Value> {
    private Node root;// 根节点
    private int N;

    // 节点类
    private class Node{
        public Key key;
        public Value value;
        public Node left;
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public int size(){
        return N;
    }

    /**
     * 例如： key=1 value=张三 root=null （node1）
     *      key=2 value=李四 root=node1（node2）：
     *          node1——key=1，2，李四 node1.left = node2
     *                  tree —— 1_张三
     *
     *     key=3 value=王五 root=node1 root.right=node2
     *
     * @param key
     * @param value
     */
    // 向树中添加元素
    public void put(Key key, Value value){
        // node1，2，李四
        // node1，3，王五
        root = put(root, key, value);
    }
    // 向某个树添加元素
    public Node put(Node x,Key key, Value value){
        // 如果x为空
        if (x==null){
            N++;
            return new Node(key,value,null,null);
        }

        // 如果x不为空
        // 比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            // x.right = null，2，李四
            // 如果子树的键要大于key，则继续找x节点的右子树
            x.right = put(x.right,key,value);

            // x.right —— node2
            // 经过回调重新赋予了子树节点

            // x.right（node2）：key=2 value=李四
            // 再次调用，直到找到子树为null，重新赋予该子树的节点键和值

        }else if (cmp<0){
            // 如果子树的键要小于key，则继续找x节点的左子树
            x.left = put(x.left,key,value);
        }else {
            // 如果子树的键要等于key，则替换value
            x.value = value;
        }
        return x;
    }

    // 根据对应的key查找到对应的值
    public Value get(Key key){
        return get(root,key);
    }
    public Value get(Node x,Key key){
        // x为null
        if (x==null){
            return null;
        }else {
            // x不为null

            // 比较键的大小
            int cmp = key.compareTo(x.key);
            if (cmp>0){
                // 如果子树的键要大于key，则继续找x节点的右子树
                return get(x.right,key);
            }else if (cmp<0){
                // 如果子树的键要小于key，则继续找x节点的左子树
                return get(x.left,key);
            }else {
                // 如果子树的键要等于key，则替换value
                return x.value;
            }
        }
    }

    // 删除树种key对应的value
    public void delete(Key key){
        delete(root,key);
    }
    public Node delete(Node x,Key key){
        // 1 找到被删除的节点
        if (x==null){
            // 1.1 x树为null
            return null;
        }
        // 1.2 x树不为null
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            // 1.2.1 如果子树的键要大于key，则继续找x节点的右子树
            x.right = delete(x.right,key);

        }else if (cmp<0){
            // 1.2.2 如果子树的键要小于key，则继续找x节点的左子树
            x.left = delete(x.left,key);
        }else {
            // 2 删除x节点的键，完成真正的删除操作
            // 6 元素个数-1
            N--;
            // 2.1 找到右子数中最小的节点
            if (x.right == null){
                return x.left;
            }

            // 2.2 找到左子树中最大节点
            if (x.left == null){
                return x.right;
            }

            // 2.3 找到最小节点
            Node minNode = x.right;
            while (minNode.left != null){
                minNode = minNode.left;
            }

            // 2.4 删除右子数中最小的节点
            Node n = x.right;
            while (n.left != null){
                if (n.left.left==null){
                    n.left = null;
                }else
                {
                    n = n.left;
                }
            }

            // 3 让x节点的左子树成为minNode的左子树
            minNode.left = x.left;
            // 4 让x节点的右子树成为minNode的右子树
            minNode.right = x.right;
            // 5 让x节点的父节点指向minNode
            x = minNode;
        }

        return x;
    }

    // 查找整个树种最小的键
    public Key min(){
        return min(root).key;
    }
    // 在指定树中找出最小键所在的节点
    public Node min(Node x){
        if (x.left != null){
            return min(x.left);
        }else {
            return x;
        }
    }
    
    // 查找整个树种最大的键
    public Key max(){
        return min(root).key;
    }
    // 在指定树中找出最大键所在的节点
    public Node max(Node x){
        if (x.right != null){
            return min(x.right);
        }else {
            return x;
        }
    }
    
}

/**
* 模拟对折过程，产生树
* @param n 对折次数
* @return
*/
public static Node<String> createTree(int n){
    // 定义根节点
    Node<String> root =null;

    for (int i = 0; i < n; i++) {
        // 1. 当前树为空
        if (i==0){
            root = new Node<>("down",null,null);
            continue;
        }

        // 2. 当前树不为空
        // 定义一个辅助队列，通过层序遍历思想找到叶子节点，给叶子节点添加子节点
        Queue<Node> queue = new Queue<>();
        queue.enqueue(root);

        // 3. 循环遍历队列
        while (!queue.isEmpty()){
            // 从队列中弹出节点
            Node<String> tmp = queue.dequeue();

            // 如果有左子节点，则把左子系欸但放入到队列中
            if (tmp.left != null){
                queue.enqueue(tmp.left);
            }

            // 如果有右子节点，则把左子系欸但放入到队列中
            if (tmp.right != null){
                queue.enqueue(tmp.right);
            }
            // 如果左右两个子节点都没有，那么该节点为叶子节点，只需要给该节点添加左子节点和右子节点
            if (tmp.right == null && tmp.left == null){
                tmp.left = new Node<String>("down",null,null);
                tmp.right = new Node<String>("up",null,null);

            }
        }
    }
    return root;
}

// 打印树中的全部节点
public static void printTree(Node<String> root){
    // 使用中序遍历
    if (root==null){
        return;
    }

    // 打印左子树的每个节点
    if(root.left!=null){
        printTree(root.left);
    }

    // 打印当前节点
    System.out.print(root.item="  ");
    // 打印右子树的每个节点
    if(root.right!=null){
        printTree(root.right);
    }
}


// 节点类
public static class Node<T>{
    public T item;
    public Node left;
    public Node right;

    public Node(T item, Node left, Node right) {
        this.item = item;
        this.left = left;
        this.right = right;
    }
}