3、二叉树

最后更新于:2022-04-02 06:11:19

  树是一种非线性表数据结构,树的基本概念如下所列。   (1)结点高度:结点到叶子结点的最长路径(即边数)。例题:[112\. 路径总和](https://leetcode-cn.com/problems/path-sum/)。   (2)结点深度:根结点到这个结点所经历的边的个数。例题:[104\. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)。   (3)结点层数:结点深度加 1。   (4)树的高度:根结点的高度。例题:[面试题 04.02. 最小高度树](https://leetcode-cn.com/problems/minimum-height-tree-lcci/)。   后面几张这种类型的图都来源于《[数据结构与算法之美](https://time.geekbang.org/column/126)》。 :-: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/50/f8/50f89510ad1f7570791dd12f4e9adeb4_1142x570.jpg =600x) 图 2   (5)二叉树:只包含左右两个子结点的树(编号1)。   (6)满二叉树:所有分支结点都存在左右子树,并且所有叶子结点都在同一层上(编号2)。例题:[894\. 所有可能的满二叉树](https://leetcode-cn.com/problems/all-possible-full-binary-trees/)。   (7)完全二叉树:叶子结点都在最底下两层,最后一层的叶子结点都靠左排列,并且除了最后一层,其余结点个数都要达到最大(编号3)。例题:[222\. 完全二叉树的结点个数](https://leetcode-cn.com/problems/count-complete-tree-nodes/)。 :-: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/09/c2/09c2972d56eb0cf67e727deda0e9412b_1142x635.jpg =600x) 图 3 ## 一、二叉树 **1)实现**   有两种方法存储一棵二叉树,第一种是基于指针的链式存储法,[如下所示](https://codepen.io/strick/pen/LYGMrVO)。 ~~~ class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } class TreeList { constructor(datas) { this.root = null; datas.forEach((value) => { const node = new Node(value); if (this.root == null) { this.root = node; return; } this.insert(this.root, node); }); } insert(parent, child) { if (parent.data > child.data) { parent.left === null ? (parent.left = child) : this.insert(parent.left, child); return; } parent.right === null ? (parent.right = child) : this.insert(parent.right, child); } } ~~~   第二种是基于数组的顺序存储法。 ~~~ left = 2 * index + 1; //左结点下标 right = 2 * index + 2; //右结点下标 ~~~   例题:LeetCode的[236\. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/),递归的在左右子树中查找两个指定的结点,最后判断公共祖先所在的位置。在当前结点的左子树,或在其右子树,又或者它就是两种的公共祖先。 **2)遍历**   二叉树的遍历有四种([示例如下](https://codepen.io/strick/pen/mdVaKVz)):   (1)前序:先访问当前结点,然后访问左子树,再访问右子树。 ~~~ preOrder(root = this.root) { //前序 if (!root) { return; } console.log(root.data); this.preOrder(root.left); this.preOrder(root.right); } ~~~ :-: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/7d/99/7d995a99dadab9fa481a5e17cd4cc8d0_555x419.png =400x) 图 4   面试题28[对称二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)。前序遍历的变种是先访问右结点,再访问左结点,如果其遍历结果与前序遍历结果相同,就说明是对称的。   面试题34[二叉树中和为某一值的路径](https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/)。前序遍历首先访问根结点,在用前序遍历访问结点时,将其压入栈中,遇到叶结点,就求和判断结果是否符合要求。然后将叶结点出栈,回到父节点,继续遍历右子树,递归执行该过程。   (2)中序:先访问左子树,然后访问当前结点,再访问右子树。 ~~~ inOrder(root = this.root) { //中序 if (!root) { return; } this.midOrder(root.left); console.log(root.data); this.midOrder(root.right); } ~~~ :-: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/f7/d5/f7d50d862a6b1902fd7b20b48c6562b7_650x410.png =400x) 图 5   面试题7[重建二叉树](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)。前序遍历第一个数是根结点,中序遍历以根结点为界其两边分别是左右子树,递归构建左右子树。   面试题54[BST中第 k 大的结点](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/)。中序遍历BST,得到的序列是递增的。   (3)后序:先访问左子树,然后访问右子树,再访问当前结点。 ~~~ postOrder(root = this.root) { //后序 if (!root) { return; } this.backOrder(root.left); this.backOrder(root.right); console.log(root.data); } ~~~ :-: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/62/5d/625d7bbb11620dc27b10276f46e49ff3_546x346.png =400x) 图 6   面试题33[BST的后序遍历序列](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/)。序列的最后一个数字是根结点,左子树的结点都比根结点小,右子树的结点都比根结点大,递归执行该过程。   (4)层序:自上而下,自左至右逐层访问树的结点。利用一个辅助队列来完成层序遍历。 ~~~ levelOrder(node = this.root) { //层序 let queue = []; queue.push(node); // 根结点入队 while (queue.length) { node = queue.shift(); // 出队 console.log(node.data); // 访问该结点 if (node.left) { // 如果它的左子树不为空 queue.push(node.left); // 将左子树的根结点入队 } if (node.right) { // 如果它的右子树不为空 queue.push(node.right); // 将右子树的根结点入队 } } } ~~~   除了层序遍历之外,其余三种都采用递归的方式来遍历二叉树。   有两种图的搜索算法,也适用于树。   (1)广度优先搜索算法(Breadth-First Search,BFS)会从根结点开始遍历,先访问其所有的相邻点,就像一次访问树的一层,也就是先宽后深地访问结点,之前的层序遍历就是BFS,如下图左半部分。   (2)深度优先搜索算法(Depth-First-Search,DFS)会从根结点开始遍历,沿着路径直到这条路径最后一个叶结点被访问,接着原路回退并探索下一条路径,也就是先深度后广度地访问结点,如下图右半部分。 :-: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/0f/84/0f8439a00e30ab283ccb34d90aa329e9_962x330.png =700x)   在《[算法小抄](https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/xue-xi-shu-ju-jie-gou-he-suan-fa-de-gao-xiao-fang-fa#san-suan-fa-shua-ti-zhi-nan)》一文中曾强调先刷二叉树的LeetCode题目,因为很多难题本质上都是基于二叉树的遍历,例如LeetCode的[124 题](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)(二叉树中的最大路径和)、[105 题](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)(从前序与中序遍历序列构造二叉树)和[99 题](https://leetcode-cn.com/problems/recover-binary-search-tree/)(恢复二叉搜索树)。 **3)递归**   递归是一种应用广泛的编程技巧,如果要使用递归,需要满足三个条件。   (1)一个问题的解可以分解为几个子问题的解。   (2)这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样。   (3)存在递归终止条件,即基线条件(Base Case)。   注意,递归的关键就是找到将大问题分解为小问题的规律(推荐画出递归树),基于此写出递推公式,然后再推敲终止条件,并且需要警惕重复计算。下面是一个递归的大致模板。 ~~~ function recursion(level, param1, param2, ...) { //递归的终止条件 if(level > MAX_LEVEL) { console.log("result"); return; } //数据处理 processData(level, data1,...); //继续递归 recursion(level + 1, p1, ...); //收尾工作 reverseState(level); } ~~~   递归的数学模型就是[归纳法](https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95),其过程如下。   (1)基础情况:证明 P(b)语句成立,该步骤只需带入数字即可。   (2)声明假设:假设 P(n)语句成立。   (3)归纳步骤:证明如果 P(n)语句成立,那么 P(n+1) 语句也一定成立。   例如设计一程序,求自然数 N 的阶乘 N!。   (1)当 N=1 时,N!=1。   (2)假设 P(N)=N!,P(N+1)=(N+1)!。   (3)证明 P(N) 和 P(N+1) 的关系: ~~~ P(N+1) = (N+1)! = (N+1)×(N)×…×2×1 = (N+1)×N! = (N+1)×P(N) ~~~   根据这个公式可构造一个递归函数: ~~~ function factorial(N) { return N * factorial(N - 1); //递归部分 } ~~~   在采用数学归纳法设计递归程序后,就能摆脱每一步的递推,直接根据分析就能转化为代码。   试图想清楚整个递和归过程的做法,实际上是一种思维误区,不符合人脑平铺直叙的思维方式。 ## 二、二叉查找树   在二叉查找树(Binary Search Tree,BST)中,每个结点的值都大于左子结点,小于右子结点。当中序遍历BST时,就可在 O(n) 的时间复杂度内输出有序的结点。   BST的时间复杂度和树的高度成正比,即 O(height),经过推导后,完全二叉树的高度(height)小于等于 log2^n。   平衡二叉查找树的高度接近 logn,所以插入、删除、查找等操作的时间复杂度也比较稳定,都是 O(logn)。 **1)操作**   在BST中查找一个结点的递归算法是([代码如下所示](https://codepen.io/strick/pen/JjGwZeZ)):   (1)如果被查找的结点和根结点的值相等,则查找命中,否则就递归地的在适当的子树中继续查找。   (2)如果被查找的结点值较小就选择左子树,否则就选择右子树。 ~~~ find(data) { //查找 let node = this.root; while (node != null) { if (data == node.data) { return node; } data < node.data ? (node = node.left) : (node = node.right); } return null; } ~~~   BST插入结点的过程和查找差不多,依次比较结点值和左右子树的大小。 ~~~ insert(parent, child) { //插入 if (parent.data > child.data) { parent.left === null ? (parent.left = child) : this.insert(parent.left, child); return; } parent.right === null ? (parent.right = child) : this.insert(parent.right, child); } ~~~   在BST中查找最大和最小的结点,以最小值为例,如果根结点的左链接为空,那么一棵BST中的最小值就是根结点;如果左链接非空,那么最小值就是左子树中的最小值。 ~~~ min(node = this.root) { //最小值 if (node.left == null) return node; return this.min(node.left); } ~~~ **2)删除**   针对删除结点的子结点个数的不同,需要分类讨论([代码如下所示](https://codepen.io/strick/pen/oNbJMoK)):   (1)如果没有子结点,那么只需将父结点中,链接删除结点的指针置为 null。   (2)如果只有一个子结点,那么只需更新父结点中,链接删除结点的指针指向其子结点即可。   (3)如果包含两个子结点,那么需要先找到该结点右子树中的最小结点,替换要删除的结点;然后再删除该最小结点,由于最小结点肯定没有左子结点,因此可以使用上面两条规则删除它。 :-: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/29/9c/299c615bc2e00dc32225f4d9e3490e2c_1142x620.jpg =600x) 图 7 ~~~ del(data) { //删除 let p = this.root, //p指向要删除的结点,初始化指向根结点 parent = null; //父结点 while (p != null && p.data != data) { parent = p; data > p.data ? (p = p.right) : (p = p.left); } if (p == null) return; //没有找到 // 要删除的结点有两个子结点 if (p.left != null && p.right != null) { //查找右子树中最小结点 let minP = p.right, minParent = p; //minParent表示minP的父结点 while (minP.left != null) { minParent = minP; minP = minP.left; } p.data = minP.data; //将minP的数据替换到p中 p = minP; //下面就变成了删除minP了 parent = minParent; } // 删除结点是叶子结点或者仅有一个子结点 let child; //p的子结点 if (p.left != null) child = p.left; else if (p.right != null) child = p.right; else child = null; if (parent == null) this.root = child; // 删除的是根结点 else if (parent.left == p) parent.left = child; else parent.right = child; } ~~~ **3)数据重复**   要让BST支持重复数据,可以有两种处理方式。   (1)在每个结点中增加一个链表,把相同的值存储到链表中。   (2)将相同的值插入到结点的右子树中,作为大于这个结点来处理。 **4)平衡二叉查找树**   平衡二叉树是指任意一个结点的左右子树的高度相差不能大于 1,让整棵树左右看起来比较对称和平衡,不要出现左子树很高、右子树很矮的情况。   在下面的[示例](https://codepen.io/strick/pen/eYJbLmo)中,height()函数会自顶向下递归的计算结点的高度,isBalanced()函数会判断左右子树的高度差。 ~~~ function isBalanced(root) { if (root == null) return true; if (Math.abs(height(root.left) - height(root.right)) > 1) { return false; } return isBalanced(root.left) && isBalanced(root.right); } function height(root) { if (root == null) return 0; return Math.max(height(root.left) + 1, height(root.right) + 1); } ~~~ ## 三、堆   堆(heap)是一种特殊的树形数据结构,它有两个特性:   (1)必须是一棵完全二叉树。   (2)结点的值要大于等于或小于等于两个子结点的值。   当结点的值小于等于两个子结点的值,称之为小顶堆;当结点的值大于等于两个子结点的值,称之为大顶堆。 **1)实现**   往堆中插入一个元素后,需要继续满足堆的两个特性,这个过程叫做堆化(heapify),下面的[示例](https://codepen.io/strick/pen/bGEOxLm)在构建一个大顶堆。 ~~~ function heapify(arr, x, len) { let l = 2 * x + 1, //左结点 r = 2 * x + 2, //右结点 largest = x, temp; if (l < len && arr[l] > arr[largest]) { largest = l; } if (r < len && arr[r] > arr[largest]) { largest = r; } if (largest != x) { //交换位置 temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr, largest, len); } } const tree = [4, 5, 1, 2, 3, 6], heapSize = tree.length; for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { heapify(tree, i, heapSize); } ~~~ **2)堆排序**   堆排序是一种原地的、时间复杂度为 O(nlogn) 的不稳定排序算法。排序主要分为两个过程:一是构建堆;二是交换堆顶元素与最后一个元素的位置,[如下所示](https://codepen.io/strick/pen/pogqOMo)。 ~~~ function heapSort(arr) { let heapSize = arr.length, temp; //建堆 for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { heapify(arr, i, heapSize); } //堆排序 for (let j = heapSize - 1; j >= 1; j--) { temp = arr[0]; arr[0] = arr[j]; arr[j] = temp; heapify(arr, 0, --heapSize); } return arr; } ~~~ **3)应用**   堆有几个非常重要的应用,例如优先级队列、求Top K和求中位数。例题:[703\. 数据流中的第K大元素](https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/),[剑指 Offer 41. 数据流中的中位数](https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/)。   其中求中位数的方法很巧妙,会维护两个堆:大顶堆和小顶堆。大顶堆中存储前半部分数据,小顶堆中存储后半部分数据,且小顶堆中的数据都大于大顶堆中的数据。如果有 n 个数据:   (1)当 n 是偶数时,前 2/n​ 个数据存储在大顶堆中,后 2/n​ 个数据存储在小顶堆中。   (2)当 n 是奇数时,大顶堆就存储 2/n​+1 个数据,小顶堆中就存储 2n​ 个数据。   这样,大顶堆中的堆顶元素就是要找的中位数。 ***** > 原文出处: [博客园-数据结构和算法躬行记](https://www.cnblogs.com/strick/category/1809992.html) 已建立一个微信前端交流群,如要进群,请先加微信号freedom20180706或扫描下面的二维码,请求中需注明“看云加群”,在通过请求后就会把你拉进来。还搜集整理了一套[面试资料](https://github.com/pwstrick/daily),欢迎阅读。 ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2e1f8ecf9512ecdd2fcaae8250e7d48a_430x430.jpg =200x200)
';