数据结构---------树详解，java语言描述

亦凉 2022-01-26 14:45 222阅读 0赞

### 文章目录 ###

*  二叉树
 *   *  1.常用的二叉树概念
     *   *  1. 满二叉树
         *  2. 完美二叉树
     *  2. 二叉树的两种物理存储.
     *  3.二叉树的应用
     *   *  2.自平衡树
     *  4. 二叉树的遍历
     *  5. 二叉堆
     *   *  二叉堆的自我调整
         *  堆的代码:

# 二叉树 #

在计算机中，常常需要用到树状存储关系，比如，家族树,企业管理树等。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]  
 其中，最常用的便是二叉树了,二叉树的定义：树的每个节点最多只有两个孩子节点。(阿里二面曾考察过)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1]  
其中最有名的有两个概念：

1.  满二叉树.
2.  完美二叉树.

## 1.常用的二叉树概念 ##

### 1. 满二叉树 ###

满二叉树就是所有非叶子节点都有左右孩子，并且所有叶子节点都在同一层级上。

简单来说：就是每一层都铺满，直到下一层没有任何元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 2]

### 2. 完美二叉树 ###

完美二叉树: 对一个有n个节点的二叉树,按层级顺序编号，则所有节点的编号为1—>n,如果这个树的所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

简单来说：满二叉树是一个完美二叉树的特殊性数，下面这种就是完美二叉树的编号，如果想要保持完美，则必须始终保持这种样子。每一层都是从左到右铺满，并且最后一层可以不满(如果最后一层满，则是满二叉树)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 3]

## 2. 二叉树的两种物理存储. ##

**1.链式存储**

**2.数组**

**链式存储表达二叉树**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 4]  
链式存储很好理解，一个Node类中含有三个值，data,以及left指针和right指针.

/** * 二叉树节点 */
    class TreeNode<T> { 
        // 值，每个节点都保存一个值
        T data;
        // 指向左节点的引用
        TreeNode left;
        // 指向右节点的引用
        TreeNode right;
    }

**数组存储**

将一个数组转化为二叉树，用到的是完美二叉树的理念。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 5]  
你会发现，对于任意一个下标，将其除以2，都是其父节点所在下标.

> 比如，我们在数组中寻找13(下标：4)的父节点，除以2得到2，其中值为521，与二叉树中的节点值相等。

## 3.二叉树的应用 ##

**1. 二叉查找树**

如果对于每个节点来说，其左子树一定都要小于自身，其右子树中所有值一定都大于自身，那么这就是一棵二叉搜索树.

![1558509813689][]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 6]

在上面这棵树中，我们查找8的话，

> 15 >8, 向左子树进行递归查找
> 
> 10 > 8, 向左子树进行递归查找
> 
> 8 == 8 ,找到目标值.

总结：本质上二叉查找树就是和二分算法的思想一样.

Tip: 二叉查找树的规则和大小顺序有关，所以二叉查找树还有一个名字------二叉排序树。

### 2.自平衡树 ###

## 4. 二叉树的遍历 ##

二叉树一共有四种遍历：

1.  前序遍历
2.  中序遍历，
3.  后序遍历
4.  层级遍历

**前序遍历**

按照当前节点–>其左子树---->其右子树的顺序进行遍历。.

就以上文的二叉搜索树举例

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 7]

前序遍历的顺序

> 15,10,8,6,13,20,18,17

*  15是当前节点，然后到10，
 *  此时10是当前节点，所以其左节点为8，进入其左节点8。
 *  8是当前节点，所以下一个是6
 *  然后没有左节点了，也没有右节点了，回退到8。
 *  没有右节点，回退到10，10自身以及其左节点都被遍历过了，所以向其右节点移动。
 *  移动到13，没有左右节点。
 *  回退到15，15自身以及左节点都已经遍历过了，所以进入15的右节点：20。

![在这里插入图片描述][20190529120909713.jpg]

/** * 前序遍历 */
        public static void preOrder(TreeNode node) { 
            if(node == null) { 
                return;
            }
            System.out.println(node.data);
            // 遍历其左子树
            preOrder(node.left);
            // 遍历其右子数
            preOrder(node.right);
        }
    	/** * 前序，非递归 */
        public static void preOrderByStack(TreeNode root) { 
            Stack<TreeNode> stack = new Stack<>();
            TreeNode treeNode = root;
            while (treeNode != null || !stack.isEmpty()) { 
                while (treeNode != null) { 
                    System.out.println(treeNode.val);
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
    
                if (!stack.isEmpty()) { 
                    treeNode = stack.pop();
                    treeNode = treeNode.right;
                }
            }
        }

**中序遍历**

中序遍历则是：先到左子树，再到自身，再到右子树

![在这里插入图片描述][20190529120924643.gif]

/** * 中序遍历 */
        public static void inOrder(TreeNode node) { 
            if(node == null) { 
                return;
            }
            // 遍历其左子树
            inOrder(node.left);
            // 打印当前节点
            System.out.println(node.data);
            // 遍历其右子数
            inOrder(node.right);
        }
    	/** * 非递归中序遍历 */
        public static void inOrderByStack(TreeNode treeNode) { 
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            while (treeNode != null || !stack.isEmpty()) { 
                while (treeNode != null) { 
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
                // 打印当前节点
                res.add(treeNode.val);
                // 遍历右子树.
                if (!stack.isEmpty()) { 
                    treeNode = stack.pop().right;
                }
            }
        }

**后序遍历**

中序遍历则是：先到右子树，再到自身，再到左子树

![在这里插入图片描述][20190529120936696.gif]

/** * 后序遍历 */
        public static void postOrder(TreeNode node) { 
            if (node == null) { 
                return;
            }
            // 遍历其左子树
            postOrder(node.left);
            // 遍历其右子数
            postOrder(node.right);
            // 打印当前节点
            System.out.println(node.data);
        }
    	// 非递归后序遍历
    	 public List<Integer> postorderbyStack(TreeNode root) { 
            List<Integer> res = new ArrayList<Integer>();
            if(root == null)
                return res;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            while(!stack.isEmpty()){ 
                TreeNode node = stack.pop();
                if(node.left != null) stack.push(node.left);//和传统先序遍历不一样，先将左结点入栈
                if(node.right != null) stack.push(node.right);//后将右结点入栈
                res.add(0,node.val);                        //逆序添加结点值
            }
            return res;
        }

**层级遍历**

一层一层的遍历

\[![img][]\]([https://image.baidu.com/search/detail?ct=503316480&z=&tn=baiduimagedetail&ipn=d&word=二叉树层级遍历][https_image.baidu.com_search_detail_ct_503316480_z_tn_baiduimagedetail_ipn_d_word] 动态&step\_word=&ie=utf-8&in=&cl=2&lm=-1&st=-1&hd=&latest=&copyright=&cs=2810546668,178229406&os=4194961988,3838670747&simid=0,0&pn=7&rn=1&di=550&ln=34&fr=&fmq=1558511710264\_R&ic=&s=undefined&se=&sme=&tab=0&width=&height=&face=undefined&is=0,0&istype=2&ist=&jit=&bdtype=0&spn=0&pi=0&gsm=0&objurl=http%3A%2F%[2Fpic4.zhimg.com][]%2Fv2-0927ca68e27ca9fd6978cd6cecf4436f\_b.gif&rpstart=0&rpnum=0&adpicid=0&force=undefined)

/** * 层级遍历 */
        public static void levelOrder(TreeNode node) { 
            if (node == null) { 
                return;
            }
            // 把每一层的节点都加入到队列中，以便遍历和获取下一层的节点
            Queue<TreeNode> levelNode = new LinkedList<>();
            levelNode.add(node);
            while (levelNode.size() != 0) { 
                for (int size = levelNode.size(); size >= 0; size--) { 
                    TreeNode cur = levelNode.remove();
                    // 打印
                    System.out.print(cur + ",");
                    if (cur.left != null) { 
                        levelNode.add(cur.left);
                    }
                    if (cur.right != null) { 
                        levelNode.add(cur.right);
                    }
                }
            }
        }

## 5. 二叉堆 ##

1.  最大堆
2.  最小堆
    
     最大堆和最小堆，就是最大值和最小值在堆顶。

### 二叉堆的自我调整 ###

二叉树的多种操作.

1.  插入节点
2.  删除节点
3.  构造二叉堆

这几种操作都基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整成一个堆。接下来以最大堆为例。

**1. 插入节点**

先将节点插入到数组的最尾端，然后与其父节点进行比较，若比其大，则交换两者的位置。重复以上过程.

如图：我们插入一个比原来的最大值78还大的值88，那么88将不断上浮直到顶点。

![在这里插入图片描述][20190529121000809.gif]

**2. 删除节点**

堆只能删除堆顶元素，其删除节点的原理是：将堆顶元素与最后一个元素交换(同时size–，使其无效)，然后调整位置即可。

![在这里插入图片描述][2019052912101734.gif]

**3. 构造二叉堆**

如果能够看懂节点的插入，那么我们就有一种简单的构造方式：刚开始将节点放入堆顶，之后不断插入节点；

![在这里插入图片描述][20190529121032562.gif]

1.  第一个元素被放在堆顶(idx = 0)。
2.  第二个元素开始插入最大堆。
3.  第三个元素开始插入最大堆。
4.  第四个元素开始插入最大堆。
5.  重复以上过程

这种构造的方式很容易理解，时间复杂度为O(NlogN),因为要进行N次插入，因为对于最坏情况：从小到大的排序:每次插入都要上浮至顶点,每次上浮都要logN的操作，总共有N次插入。

那么，有没有办法只是用O(N)的时间复杂度呢？

答案是肯定的，先说思路：我们将目标值们先直接放入堆数组中(此时并不是最大堆，只是一个单纯的数组)，接着我们从倒数第二层向上遍历，每个节点判断是否需要下浮，当遍历结束时，最大值会"被迫"上浮到堆顶。

> Q ：这不还是插入，上浮嘛？为啥时间就变成了O(N)？
> 
> A : 这涉及到一个数学推导，不过我在这里简单介绍以下大概的思路。
> 
> 简单起见，我们把目标二叉堆设想为一个满二叉树，有2^k个元素，并且数组已经排好序了。
> 
> 对于最下面的一层，其不需要任何操作，所以其交换次数为: 0, 访问次数为2^(k)
> 
> 对于倒数第二层，其每一个节点都需要下移(因为我们假定其是最坏情况，已经排好序),那么交换次数为: 2^(k-2) \* 1次
> 
> 对于倒数第三层，与第二层相同，每个节点都要向下移动两次，所以交换次数为：2^(k-2) \* 2
> 
> 对于倒数第 y 层，同上，每个节点需要向下移动 y - 1次，所以交换次数为：2^(k - (y - 1) ) \* (k - 1);化简为：2^k \*((x-1)/(2\*(x-1)))–>2k \*(m / 2^m).
> 
> 问题就变成了对于ai = 2^(k) \*(i / 2i)的求和问题，我们提取2k，就变成了 i /(2^i)的求和问题。这是一个高中难度的裂项问题(大多数人都在数列题中做过)，答案是Sn = 4-（k+2）/2^(k-1), 很容易得到当k很大时，Sn为4，所以最终求和结果为: 2^k \*(Sn)—>2^k \*(4 - 0) \[当n很大时，k也很大\]----> n *(4 - 0)–>4*n
> 
> 所以最终时间复杂度为:O(n)。

![在这里插入图片描述][20190529121044461.gif]

接下来用最坏情况：\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20\}一个已经排序好的数组进行比较时间。

O（N）时间大约为10s（当然这省去了将元素放入数组的时间,不过这无关大雅.）

![在这里插入图片描述][20190529121057100.gif]

O(NlogN)时间大约为40s,如果我们有意识地忽略放入元素地时间，只看交换元素的次数，我们也能明显的感受到其速度之慢。

![在这里插入图片描述][20190529121111725.gif]

### 堆的代码: ###

在展示代码之前，我们需要明确：虽然我们一般使用链式或数组表示树，但是堆是特指要用数组表示的一种树,这是为了利用数组的访问快的优势达到一些目的。换句话说,二叉堆的所有节点都存储在数组中。

import java.util.Arrays;
    
    /** * 一个最大堆的构建过程 */
    public class upMaxHeap { 
    
        public static void main(String[] args) { 
            int[]  array = { 7, 1, 3, 10, 5, 2, 8, 9, 6};
            buildHeap(array);
            System.out.println(Arrays.toString(array));
        }
    
        /** * 构造最大堆 */
        private static void buildHeap(int[] array) { 
            // 从最后一个节点开始，依次做“下沉”调整
            for (int i = (array.length - 2) / 2; i >= 0; i--) { 
                // 每个节点都下沉，那么对于任意一个子树，其根节点都是最大值。
                downAdjust(array, i, array.length);
            }
        }
    
        /** * 将对应下标 i 下沉到对应位置，以便于对应的大值上浮 * 我们不让其交换，而是单向覆盖. */
        private static void downAdjust(int[] array, int parentIdx, int length) { 
            // 先保存当前值,
            int temp = array[parentIdx];
            int childIdx = 2 * parentIdx + 1;
            while (childIdx < length) { 
                // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子.
                if (childIdx + 1 < length && array[childIdx + 1] > array[childIdx]) { 
                    childIdx++;
                }
                if (temp > array[childIdx]) { 
                    break;
                }
                // 单项覆盖
                array[parentIdx] = array[childIdx];
                parentIdx = childIdx;
                // 子节点下标移动子节点的子节点上。
                childIdx = 2 * childIdx + 1;
            }
            // 最后覆盖。
            array[parentIdx] = temp;
        }
    }
    /** * [10, 9, 8, 7, 5, 2, 3, 1, 6] */

构建完成后，我们需要增删操作，增操作很好理解，但是删除操作，我们只需要能够删除最大值，而且在删除后依然是一个最大堆(因为最大堆一般都用于优先队列中，队列中增加的值不确定，但出队列的一定是队首的值，在优先队列中则是最值)。

import java.util.Arrays;
    
    /** * 一个最大堆. */
    public class MaxHeap { 
        int[] array;
        int size;
    
        public static void main(String[] args) { 
            int[] array = { 7, 1, 3, 10, 5, 2, 8, 9, 6};
            MaxHeap maxHeap = new MaxHeap(array);
            System.out.println("构建完成:" + maxHeap);
            maxHeap.insert(4);
            System.out.println("插入完成:" + maxHeap);
            // 移除最大值
            maxHeap.delete();
            System.out.println("删除完成:" + maxHeap);
            maxHeap.delete();
            System.out.println("删除完成:" + maxHeap);
            maxHeap.delete();
            System.out.println("删除完成:" + maxHeap);
            maxHeap.delete();
            System.out.println("删除完成:" + maxHeap);
    
        }
    
        /** * 移除堆顶元素 */
        private int delete() { 
            int temp = array[0];
            array[0] = array[size - 1];
    
            downAdjust(0);
            size--;
            return temp;
        }
    
        /** * 插入一个值 */
        private void insert(int val) { 
            if (array.length <= size) { 
                // 申请更大的内存.
                grow();
            }
            array[size++] = val;
            upAdjust(size);
        }
    	// 内存不足时，数组容量扩大.
        private void grow() { 
            int[] newArr = new int[array.length * 2];
            System.arraycopy(array, 0, newArr, 0, array.length);
            array = newArr;
        }
    
        /** * 将 下标为i的值上浮至对应位置 */
        private void upAdjust(int i) { 
            int temp = array[i];
            int parentIdx = i / 2;
            while (parentIdx > 0 && array[i] > array[parentIdx]) { 
                i = parentIdx;
                parentIdx /= 2;
            }
            array[i] = temp;
        }
    
        public MaxHeap(int[] array) { 
            this.array = array;
            size = array.length;
            adjustHeap();
        }
    
        @Override
        public String toString() { 
            StringBuilder res = new StringBuilder();
            res.append("array=[");
            for (int i = 0; i < size; i++) { 
                res.append(array[i] + " , ");
            }
            res.append("]");
            return res.toString();
        }
    
        /** * 构造最大堆 */
        private void adjustHeap() { 
            // 从最后一个节点开始，依次做“下沉”调整
            for (int i = (size - 2) / 2; i >= 0; i--) { 
                downAdjust(i);
            }
        }
    
        /** * 将对应下标 i 下沉到对应位置，以便于对应的大值上浮 */
        private void downAdjust(int parentIdx) { 
            int length = size;
            // 先保存当前值,
            int temp = array[parentIdx];
            int childIdx = 2 * parentIdx + 1;
            while (childIdx < length) { 
                // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子.
                if (childIdx + 1 < length && array[childIdx + 1] > array[childIdx]) { 
                    childIdx++;
                }
                if (temp > array[childIdx]) { 
                    break;
                }
                array[parentIdx] = array[childIdx];
                parentIdx = childIdx;
                childIdx = 2 * childIdx + 1;
            }
            array[parentIdx] = temp;
        }
    }

如果想要一个优先队列，可以通过对上述代码进行简单改变就可以完成了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]: /images/20220126/79c38de1570945eba5d786827ba90c4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1]: /images/20220126/b56c764dc2aa406791451ff7bf47e443.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 2]: /images/20220126/0250ea3822014f71b2ad425f6defee7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 3]: /images/20220126/ecea7de518644e9a8e177010a25fb557.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 4]: /images/20220126/891c5c28eeeb46ed857c880b214b3c87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 5]: /images/20220126/fd99e0016b1e4c2bae8c0b2ceec056a8.png
[1558509813689]: 
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20190529120816219.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 7]: /images/20220126/f251094c8b8d4160ad6ea466f6877e9b.png
[20190529120909713.jpg]: /images/20220126/625c1926ca2342628569f0810113ba78.png
[20190529120924643.gif]: /images/20220126/d7577f2d79324d28b5f6a547b2b02241.png
[20190529120936696.gif]: /images/20220126/db0f6fddae8d4256b89743080599b943.png
[img]: https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1558521816760&di=5ca25c9cd475351220c635fde1794a85&imgtype=0&src=http%3A%2F%2Fpic4.zhimg.com%2Fv2-0927ca68e27ca9fd6978cd6cecf4436f_b.gif
[https_image.baidu.com_search_detail_ct_503316480_z_tn_baiduimagedetail_ipn_d_word]: https://image.baidu.com/search/detail?ct=503316480&z=&tn=baiduimagedetail&ipn=d&word=%E4%BA%8C%E5%8F%89%E6%A0%91%E5%B1%82%E7%BA%A7%E9%81%8D%E5%8E%86
[2Fpic4.zhimg.com]: http://2Fpic4.zhimg.com
[20190529121000809.gif]: /images/20220126/37429c86d2d845bebda61e78a2cc9dd1.png
[2019052912101734.gif]: /images/20220126/fdf6392109c34e8391492e633eb4b528.png
[20190529121032562.gif]: /images/20220126/59203070a66e4e2d937dc38b052595d6.png
[20190529121044461.gif]: /images/20220126/d5a7c6be47b04da0ae71c36413dacf77.png
[20190529121057100.gif]: /images/20220126/ac26dcf96bcd4538aaed1ffc99438a5f.png
[20190529121111725.gif]: /images/20220126/ef1adab4687e447a99cdf67a04d1451c.png