1、数据结构之：树的相关定义和二叉树

数据结构之：树的相关定义和二叉树

一、相关定义

1.1、树的定义

·N个节点组成的具有层次关系的优先集合，其中N>=0,当N=0时称为空树，在任意非空树中：
1、有且只有一个根节点，根节点是没有父节点的
2、每个节点都有0个或多个子节点
3、除根节点之外的其余节点可分为互不相交的有限集，其中每个集合本身亦是一棵树，
称为原树的子树

·节点：上图中的每一个圈都是一个节点
·根节点：上图中的A就是根节点
·父节点：A就是BC的父节点，B就是DEF的父节点，G是I的父节点
·子节点：B和C是A的子节点，DEF是B的子节点，GH是C的子节点
·兄弟节点：有同一个父节点的节点即兄弟节点，DEF就是兄弟节点，BC也是兄弟节点
·叶子结点：没有子节点的节点就是叶子结点
·节点的度：节点的子节点个数，B的度是3，A的度是2，C的度是2，G的度是1
·节点层次：从根节点开始，根为第一层，跟的子节点为第二层，依次类推
·树的深度：树中节点的最大层次就是根的深度

1.2、二叉树的定义

·N个节点组成的具有层次关系的有限集合，其中N>=0,当N=0时称为空树
1、每个节点最多有2个子节点，所以二叉树中不存在度大于2的节点
2、左子树和右子树是有顺序的，次序不能任意颠倒
3、即使树中某个节点只有1个子节点，也要区分它是左子树还是右子树

常见的二叉树：满二叉树、完全二叉树、二叉查找树、平衡二叉树、红黑树

1.2.1、满二叉树和完美二叉树定义

·满二叉树：
除了叶子节点，每个节点的度都为2,不存在度为1的节点
·完美二叉树
每一层节点的数都达到最大值（第一层1个节点，第二层2个节点，第三层4个节点，
第四层8个节点，依次类推）

1.2.2、完全二叉树

1、如果二叉树中除去最后一层节点外为满二叉树
2、且最后一层的节点一次从左到右分布

二、二叉查找树

·二叉查找树 又叫做 二叉排序树、二叉搜索树

·二叉查找树定义：
1、若左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2、若右子树不为空，则右子树上所有节点的值均大于它的根节点的值
3、左、右子树也分别为二叉排序树
4、没有键值相等的节点

·前驱结点定义：
1、前驱结点是小于该节点的最大节点
2、对二叉树中序遍历，遍历后的顺序，当前节点的前一个节点为该节点的前驱结点

·后继节点定义：
1、后继节点是大于该节点的最小节点
2、对二叉树中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点


·操作：查找节点
1、若根节点的关键字值等于查找的关键字，成功
2、否则，若小于根节点的关键字值，递归查左子树
3、若大于根节点的关键字值，递归查右子树
4、若子树为空，查找不成功

·操作：遍历节点
1、前序遍历：根节点--左子树--右子树
   8  5  3  2  4  7  6  11  9  12
2、中序遍历：左子树--根节点--右子树
   2  3  4  5  6  7  8  9  11  12 
3、后序遍历：左子树--右子树--根节点
   2  4  3  6  7  5  9  12  11  8
4、层序遍历：一层一层遍历（从上到下 从左到右）
   8  5  11  3  7  9  12  2  4  6

·操作：插入节点
假入插入节点为N
1、若果根节点为空,直接把N设为根节点
2、如果N小于根节点，则把N插入根节点的左子树，将根节点的左子树作为根节点，回到第一步
3、如果N大于根节点，则把N插入根节点的右子树，将根节点的右子树作为根节点，回到第一步
4、如果N等于根节点，直接返回根节点

·操作：删除节点
1、叶子节点：直接删除
2、节点有一个左子节点：删除该节点，让左子节点替代自己
3、节点有一个右子节点：删除该节点，让右子节点替代自己
4、节点有两个子节点：删除该节点，让该节点左子树中最大的或者右子树中最小的替代自己
                 （即让该节点的前驱结点或后继节点来替代自己）

/**
 * 节点
 */
@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
public class Node<K extends Comparable,V> {
    private K key;
    private V value;
    private Node leftNode;
    private Node rightNode;
    private Node parentNode;
}

/**
 * 树工具类
 */
public class TreeOperation {

    // 用于获得树的层数
    public static int getTreeDepth(Node root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeftNode()), getTreeDepth(root.getRightNode())));
    }


    private static void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.getLeftNode() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.getLeftNode(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.getRightNode() != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.getRightNode(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }


    public static void show(Node root) {
        if (root == null) System.out.println("EMPTY!");
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth/ 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

/**
 * 二叉查找树
 */
@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
public class BinaryTree<K extends Comparable,V> {

    private Node<K,V> root;

    /**
     * 插入
     */
    public void insert(K key,V value){
        //根节点为null,直接设为根节点
        if(root==null){
            this.root = new Node<>(key,value,null,null,null);
            return;
        }

        //查找要插入的节点的父节点
        Node parentNode = null;
        Node rootNode = this.root;
        int compRes = 0;
        while(rootNode!=null){
            parentNode = rootNode;
            compRes = key.compareTo(rootNode.getKey());
            if(compRes>0){
                //放入右子树
                rootNode = rootNode.getRightNode();
            }else if(compRes==0){
                //相等，替换value
                rootNode.setValue(value);
                return;
            }else{
                //放入左子树
                rootNode = rootNode.getLeftNode();
            }
        }

        //插入
        Node tempNode = parentNode;
        if(compRes>0){
            parentNode.setRightNode(new Node<K,V>(key,value,null,null,tempNode));
        }else{
            parentNode.setLeftNode(new Node<K,V>(key,value,null,null,tempNode));
        }
    }

    /**
     * 查找
     */
    public Node findNode(K key){
        if(this.root==null){
            return null;
        }
        Node rootNode = this.root;
        while(rootNode!=null){
            int compRes = key.compareTo(rootNode.getKey());
            if(compRes<0){
                rootNode = rootNode.getLeftNode();
            }else if(compRes==0){
                return rootNode;
            }else{
                rootNode = rootNode.getRightNode();
            }
        }
        return null;
    }


    /**
     * 前序遍历NLR: 根节点--左子树--右子树
     * @param root
     */
    public void preOrderTraversal(Node root){
        if(root!=null){
            //根节点
            System.out.print(root.getKey()+"  ");
            //左子树
            if(root.getLeftNode()!=null){
                preOrderTraversal(root.getLeftNode());
            }
            //右子树
            if(root.getRightNode()!=null){
                preOrderTraversal(root.getRightNode());
            }
        }
    }


    /**
     * 中序遍历LNR: 左子树--根节点--右子树
     * @param root
     */
    public void inorderTraversal(Node root){
        if(root!=null){
            //左子树
            if(root.getLeftNode()!=null){
                inorderTraversal(root.getLeftNode());
            }
            //根节点
            System.out.print(root.getKey()+"  ");
            //右子树
            if(root.getRightNode()!=null){
                inorderTraversal(root.getRightNode());
            }
        }
    }


    /**
     * 后序遍历LRN: 左子树--右子树--根节点
     * @param root
     */
    public void postorderTraversal(Node root){
        if(root!=null){
            //左子树
            if(root.getLeftNode()!=null){
                postorderTraversal(root.getLeftNode());
            }
            //右子树
            if(root.getRightNode()!=null){
                postorderTraversal(root.getRightNode());
            }
            //根节点
            System.out.print(root.getKey()+"  ");
        }
    }

    /**
     * 层序遍历：一层一层遍历（从上到下 从左到右）
     * @param root
     */
    public void levelOrderTraversal(Node root){
        if(root!=null){
            Queue<Node> queue = new LinkedList();
            queue.add(root);
            while (!queue.isEmpty()){
                Node removeNode = queue.remove();
                System.out.print(removeNode.getKey()+"  ");
                Node leftNode = removeNode.getLeftNode();
                if(leftNode!=null){
                    queue.add(leftNode);
                }
                Node rightNode = removeNode.getRightNode();
                if(rightNode!=null){
                    queue.add(rightNode);
                }
            }
        }
    }

    /**
     * 删除：
     * 1、叶子节点：直接删除
     * 2、节点有一个左子节点：删除该节点，让左子节点替代自己
     * 3、节点有一个右子节点：删除该节点，让右子节点替代自己
     * 4、节点有两个子节点：删除该节点，让该节点左子树中最大的或者右子树中最小的替代自己
     *                  （即让该节点的前驱结点或后继节点来替代自己）
     */
    public void deleteNode(K key){
        Node select = findNode(key);
        if(select!=null){
            if(select.getLeftNode()==null && select.getRightNode()==null){
                //1、删除的是叶子节点
                Node parentNode = select.getParentNode();
                if(parentNode==null){
                    //删除的节点是根节点
                    this.root = null;
                }else{
                    //删除的节点不是根节点
                    if(parentNode.getLeftNode()==select){
                        //删除的节点是其父节点的左节点，将其父节点的左节点置为空
                        parentNode.setLeftNode(null);
                    }else{
                        //删除的节点是其父节点的右节点，将其父节点的右节点置为空
                        parentNode.setRightNode(null);
                    }
                }
            }else if(select.getLeftNode()==null || select.getRightNode()==null){
                //2、删除的节点有一个子节点
                Node parentNode = select.getParentNode();
                Node childrenNode = select.getLeftNode()!=null ? select.getLeftNode() : select.getRightNode();
                if(parentNode==null){
                    //删除的节点是根节点
                    childrenNode.setParentNode(null);
                    this.root = childrenNode;
                }else{
                    //删除的节点不是根节点
                    if(parentNode.getLeftNode()==select){
                        //删除的节点是其父节点的左节点，将其子节点设置为父节点的左节点
                        parentNode.setLeftNode(childrenNode);
                    }else{
                        //删除的节点是其父节点的右节点，将其子节点设置为父节点的右节点
                        parentNode.setRightNode(childrenNode);
                    }
                    //将其子节点的父节点变更为其父节点
                    childrenNode.setParentNode(parentNode);
                }


            }else{
                //3、删除的节点有两个子节点--我们采用将删除节点的后继节点替代自己
                //既然是后继节点那么后继节点要么没有子节点要么只有右节点
                Node parentNode = select.getParentNode();
                //因为删除的节点有两个子节点，所以后继几点肯定不为null
                Node nextNode = findNextNode(select);
                //后继节点的父节点：--后继节点肯定是其父节点的左子节点（后继节点肯定有父节点）
                //后继节点的父节点==删除节点
                //后继节点的父节点!=删除节点
                Node nextNodeParentNode = nextNode.getParentNode();
                //后继节点的子节点(后继节点只能有右子节点或者没有子节点)
                Node nextNodeChildrenNode = nextNode.getRightNode();

                //3.1、后继接点和删除节点互换
                if(parentNode==null){
                    //删除的节点是根节点--后继节点替代自己
                    nextNode.setParentNode(null);
                    this.root = nextNode;
                }else{
                    //删除的节点不是根节点--后继节点替代自己
                    nextNode.setParentNode(parentNode);
                    if(parentNode.getLeftNode()==select){
                        parentNode.setLeftNode(nextNode);
                    }else{
                        parentNode.setRightNode(nextNode);
                    }
                }

                //删除节点的左子树成为后继节点的左子树
                if(select.getLeftNode()!=null){
                    select.getLeftNode().setParentNode(nextNode);
                    nextNode.setLeftNode(select.getLeftNode());
                }

                //3.2、后继节点的父节点和后继节点的子节点挂钩
                if(nextNodeChildrenNode==null){
                    //后继节点没有子节点
                    if(nextNodeParentNode==select){
                        //后继节点的父节点==删除节点(不做任何操作)
                    }else{
                        //后继节点的父节点!=删除节点(设置后继节点的父节点的左子树为null)
                        nextNodeParentNode.setLeftNode(null);
                    }
                }else{
                    //后继节点有子节点
                    if(nextNodeParentNode==select){
                        //后继节点的父节点==删除节点(不做任何操作)
                    }else{
                        //后继节点的父节点!=删除节点
                        //(设置后继节点的父节点的左子树为后继节点的子节点)
                        //(设置后继节点的子节点的父节点为后继节点的父节点)
                        nextNodeParentNode.setLeftNode(nextNodeChildrenNode);
                        nextNodeChildrenNode.setParentNode(nextNodeParentNode);
                    }
                }

                //3.3、删除节点的右子树成为后继节点的右子树
                if(select.getRightNode()!=nextNode){
                    select.getRightNode().setParentNode(nextNode);
                    nextNode.setRightNode(select.getRightNode());
                }

            }
        }
    }

    /**
     * 查询后继节点
     */
    public Node  findNextNode(Node currentNode){
        if(currentNode!=null){
            Node nextNode = currentNode.getRightNode();
            if(nextNode!=null){
                while(nextNode.getLeftNode()!=null){
                    nextNode = nextNode.getLeftNode();
                }
                return nextNode;
            }
        }
        return null;
    }


    /**
     * 查询前驱结点
     */
    public Node findPreNode(Node currentNode){
        if(currentNode!=null){
            Node preNode = currentNode.getLeftNode();
            if(preNode!=null){
                while(preNode.getRightNode()!=null){
                    preNode = preNode.getRightNode();
                }
                return preNode;
            }
        }
        return null;
    }


    public static void main(String[] args) {
        BinaryTree  bt = new BinaryTree();
        bt.insert(8,8);
        bt.insert(5,5);
        bt.insert(11,11);
        bt.insert(3,3);
        bt.insert(2,2);
        bt.insert(4,4);
        bt.insert(7,7);
        bt.insert(6,6);
        bt.insert(9,9);
        bt.insert(12,12);
        System.out.println("**********打印树1***********");
        TreeOperation.show(bt.getRoot());

        System.out.println("**********查找***********");
        Node node = bt.findNode(7);
        System.out.println(node.getKey());
        System.out.println("***********前序遍历**********");
        bt.preOrderTraversal(bt.getRoot());
        System.out.println("\n**********中序遍历***********");
        bt.inorderTraversal(bt.getRoot());
        System.out.println("\n**********后序遍历***********");
        bt.postorderTraversal(bt.getRoot());
        System.out.println("\n**********层序遍历***********");
        bt.levelOrderTraversal(bt.getRoot());

        BinaryTree  bt2 = new BinaryTree();
        bt2.insert(8,8);
        bt2.insert(7,7);
        bt2.insert(4,4);
        bt2.insert(12,12);
        bt2.insert(2,2);
        bt2.insert(5,5);
        bt2.insert(9,9);
        bt2.insert(14,14);
        bt2.insert(1,1);
        bt2.insert(3,3);
        bt2.insert(10,10);
        bt2.insert(13,13);
        bt2.insert(16,16);
        bt2.insert(15,15);
        System.out.println("\n**********打印树2***********");
        TreeOperation.show(bt2.getRoot());
        System.out.println("\n**********删除节点***********");
        bt2.deleteNode(14);
        TreeOperation.show(bt2.getRoot());

    }
}

##测试：
**********打印树1***********
            8            
         /     \         
      5           11     
    /   \       /   \    
  3       7   9       12 
 / \     /               
2   4   6                
**********查找***********
7
***********前序遍历**********
8  5  3  2  4  7  6  11  9  12  
**********中序遍历***********
2  3  4  5  6  7  8  9  11  12  
**********后序遍历***********
2  4  3  6  7  5  9  12  11  8  
**********层序遍历***********
8  5  11  3  7  9  12  2  4  6  
**********打印树2***********
                        8                        
                    /       \                    
                7               12               
             /               /     \             
          4               9           14         
        /   \               \       /   \        
      2       5               10  13      16     
     / \                                 /       
    1   3                               15       

**********删除节点***********
                        8                        
                    /       \                    
                7               12               
             /               /     \             
          4               9           15         
        /   \               \       /   \        
      2       5               10  13      16     
     / \                                         
    1   3   

三、平衡二叉树

当我们录入二叉查询树的时候可能会出现  2->3->4->5的链表结构，345全部成了2的右子树

·二叉平衡树AVL
平衡二叉树的每个节点的左子树和右子树的高度最多差1

·平衡因子
该节点左子树的高度-该节点右子树的高度，即左右子树的高度差

【减小的二叉树的高度，这样查询的时候速度更快】

二叉树四种需要调整平衡的情况