【大数据】学习笔记 1 Java SE 第12章集合的重要接口 12.5 二叉树(了解)

柔光的暖阳◎ 2024-03-22 14:06 65阅读 0赞

### 【大数据】学习笔记 ###

#### 文章目录 ####

*   *  【大数据】学习笔记
     *   *  1 Java SE
         *   *  第12章 集合的重要接口
             *   *  12.5 二叉树(了解)
                 *   *  12.5.1 二叉树的基本概念
                     *  12.5.2 二叉树的遍历
                     *  12.5.3 经典二叉树
                     *  12.5.4 二叉树的实现

![在这里插入图片描述][eb4031ca489f437fa692c30f57eae681.png_pic_center]

#### 1 Java SE ####

##### 第12章 集合的重要接口 #####

###### 12.5 二叉树(了解) ######

###### 12.5.1 二叉树的基本概念 ######

二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

![在这里插入图片描述][cee6b525427341e6b4bdc1ccd31e44f7.png_pic_center]

###### 12.5.2 二叉树的遍历 ######

*  前序遍历：中左右（根左右）
 *  中序遍历：左中右（左根右）
 *  后序遍历：左右中（左右根）

![在这里插入图片描述][509b224345784dc0a3a10dc40b418da3.png_pic_center]

前序遍历：ABDHIECFG

中序遍历：HDIBEAFCG

后序遍历：HIDEBFGCA

###### 12.5.3 经典二叉树 ######

1.  满二叉树： 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方，总的结点个数是2的n次方-1

![在这里插入图片描述][1595b37215734dc7bb0fa79b2b8d7521.png_pic_center]

1.  完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。

![在这里插入图片描述][c0bbbc0e6b9549f6887f51b18f89c6ea.png_pic_center]

1.  平衡二叉树：平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树， 但不要求非叶节点都有两个子结点 。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。例如红黑树的要求：

*  节点是红色或者黑色
 *  根节点是黑色
 *  每个叶子的节点都是黑色的空节点（NULL）
 *  每个红色节点的两个子节点都是黑色的。
 *  从任意节点到其每个叶子的所有路径都包含相同的黑色节点数量。

当我们插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理：

1.  recolor ：将某个节点变红或变黑
2.  rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）

使得它继续满足以上以上的5个要求。

![在这里插入图片描述][f6cd2272b8334d359dc38451604bb38c.png_pic_center]

例如：插入了结点21之后，红黑树处理成：

![在这里插入图片描述][e330a850318f4ed49cff87bde2a048ec.png_pic_center]

###### 12.5.4 二叉树的实现 ######

普通二叉树：

public class BinaryTree<E>{
        
        private Node root; //二叉树的根结点
        private int total;//结点总个数
        
        private class Node{
        
            Node parent;
            Node left;
            E data;
            Node right;
            
            public Node(Node parent, Node left, E data, Node right) {
        
                this.parent = parent;
                this.left = left;
                this.data = data;
                this.right = right;
            }
    	}
    }

TreeMap红黑树：

public class TreeMap<K,V> {
        
        private transient Entry<K,V> root;
        private transient int size = 0;
        
    	static final class Entry<K,V> implements Map.Entry<K,V> {
        
            K key;
            V value;
            Entry<K,V> left;
            Entry<K,V> right;
            Entry<K,V> parent;
            boolean color = BLACK;
    
            /**
             * Make a new cell with given key, value, and parent, and with
             * {@code null} child links, and BLACK color.
             */
            Entry(K key, V value, Entry<K,V> parent) {
        
                this.key = key;
                this.value = value;
                this.parent = parent;
            }
        }
    }

[eb4031ca489f437fa692c30f57eae681.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/1f8e363ca90e4f0e938755dfffc2a54f.png
[cee6b525427341e6b4bdc1ccd31e44f7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/e5740050abea4758b2a34c77bfcfad60.png
[509b224345784dc0a3a10dc40b418da3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b121a0335574431e9d7d9f24b73297dd.png
[1595b37215734dc7bb0fa79b2b8d7521.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d9e44aa7cab042db8003b94f63ae969c.png
[c0bbbc0e6b9549f6887f51b18f89c6ea.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/ed179448f8454c9387665011d5b7c3ee.png
[f6cd2272b8334d359dc38451604bb38c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/bb27a89950894a99922bc5b2be22b256.png
[e330a850318f4ed49cff87bde2a048ec.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d2bb3038950f4864a9de36a8a5b1371e.png