二叉树的那些知识点

谁践踏了优雅 2022-10-16 12:23 166阅读 0赞

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

树型结构是一类非常重要的非线性结构，是以分支关系定义的层次结构。

在日常的开发中，也会遇到将数组转换为树形结构的场景。

const data = [{ 
      id: 1,
      name: '1',
    }, { 
      id: 2,
      name: '1-1',
      parentId: 1
    }, { 
      id: 3,
      name: '1-1-1',
      parentId: 2
    }, { 
      id: 4,
      name: '1-2',
      parentId: 1
    }, { 
      id: 5,
      name: '1-2-2',
      parentId: 4
    }, { 
      id: 6,
      name: '1-1-1-1',
      parentId: 3
    }, { 
      id: 7,
      name: '2',
    }]

把父子关系的数组转换为树形结构

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5Y-q54uX_size_20_color_FFFFFF_t_70_g_se_x_16]

二叉树（Binary Tree）的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分（其次序不能任意颠倒。）

![img][]

### 构造一棵二叉树 ###

// 二叉树构造函数
    function BinaryTree() { 
      // 节点的构造函数
      let Node = function (key) { 
        this.key = key; // 节点的值
        this.left = null; // 左子树节点
        this.right = null; // 右子树节点
      }
    
      // 根节点
      let root = null;
    
      // 插入root的子节点
      let insertNode = function (parentNode, childNode) { 
        // 左子树构造
        if (childNode.key < parentNode.key) { 
          // 为空时赋值，否则继续延伸
          if (parentNode.left === null) { 
            parentNode.left = childNode;
          } else { 
            insertNode(parentNode.left, childNode);
          }
        } else {  // 右子树的构造 childNode.key > parentNode.key
          if (parentNode.right === null) { 
            parentNode.right = childNode;
          } else { 
            insertNode(parentNode.right, childNode);
          }
        }
    
      }
    
      this.getRoot = function () { 
        return root;
      }
    
      // 插入节点的实例方法
      this.insert = function (key) { 
        var thisNode = new Node(key);
    
        // 根节点赋值
        if (root === null) { 
          root = thisNode;
        } else { 
          // 插入子节点
          insertNode(root, thisNode);
        }
      }
    }
    
    let nodes = [8, 3, 10, 1, 5, 14, 4, 6, 13];
    let binaryTree = new BinaryTree();
    nodes.forEach(key => { 
      binaryTree.insert(key);
    });
    
    console.log(binaryTree.getRoot());

### 遍历表达法 ###

遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。

遍历表达法有4种方法：先序遍历、中序遍历、后序遍历、层次遍历

其先序遍历（又称先根遍历）为ABDECF（根-左-右）

其中序遍历（又称中根遍历）为DBEAFC（左-根-右）（仅二叉树有中序遍历）

其后序遍历（又称后根遍历）为DEBFCA（左-右-根）

其层次遍历为ABCDEF（同广度优先搜索）

![img][img 1]

### JS 中的二叉树 ###

let tree = { 
      value: "a",
      left: { 
        value: 'a1',
        left: { 
          value: 'a11',
        },
        right: { 
          value: 'b1',
          left: { 
            value: 'b11',
          },
          right: { 
            value: 'b12',
          }
        }
      },
      right: { 
        value: 'c1',
        left: { 
          value: 'c11',
        },
        right: { 
          value: 'c12',
        }
      }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDc3NzIx_size_16_color_FFFFFF_t_70_pic_center 1]

### 深度优先遍历 ###

#### 先序遍历 ####

##### 递归遍历 #####

let frontDFS = function(tree) { 
      let result = []
      let dfs = function(node) { 
        if (node) { 
          result.push(node.value)
          dfs(node.left)
          dfs(node.right)
        }
      }
      dfs(tree)
      return result
    }
    // ["a", "a1", "a11", "b1", "b11", "b12", "c1", "c11", "c12"]

> 先遍历根结点，将值存入数组，然后递归遍历：先左结点，将值存入数组，继续向下遍历；直到（二叉树为空）子树为空，则遍历结束；然后再回溯遍历右结点，将值存入数组，这样递归循环，直到（二叉树为空）子树为空，则遍历结束。

##### 非递归遍历 #####

**利用栈：将遍历到的结点都依次存入栈中，拿结果时从栈中访问**

let frontDFS = function(tree) { 
      let result = []
      let stack = []
      stack.push(tree)
      // 栈中的数据为空
      while(stack.length) { 
        // 取栈中最后一个
        let node = stack.pop()
        result.push(node.value)
        // 先压入右子树
        if (node.right) stack.push(node.right)
        // 后压入左子树
        if (node.left) stack.push(node.left)
      }
      return result
    }
    // ["a", "a1", "a11", "b1", "b11", "b12", "c1", "c11", "c12"]

> 1.  初始化一个栈，将根节点压入栈中
> 2.  当栈为非空时，循环执行步骤3到4，否则执行结束
> 3.  从队列取得一个结点（取的是栈中最后一个结点），将该值放入结果数组
> 4.  若该结点的右子树为非空，则将该结点的右子树入栈，若该结点的左子树为非空，则将该结点的左子树入栈；（**注意：先将右结点压入栈中，后压入左结点**，从栈中取得时候是取最后一个入栈的结点，而先序遍历要先遍历左子树，后遍历右子树）

#### 中序遍历 ####

##### 递归遍历 #####

let inorderDFS = function(tree) { 
      let result = []
      let dfs = function(node) { 
        if (node) { 
          dfs(node.left)
          result.push(node.value)
          dfs(node.right)
        }
      }
      dfs(tree)
      return result
    }
    // ["a11", "a1", "b11", "b1", "b12", "a", "c11", "c1", "c12"]

> 先递归遍历左子树，从最后一个左子树开始存入数组，然后回溯遍历双亲结点，再是右子树，这样递归循环。

##### 非递归遍历 #####

let inorderDFS = function(node) { 
      let result = []
      let stack = []
      while(stack.length || node) { 
        if (node) { 
          stack.push(node)
          node = node.left
        } else { 
          node = stack.pop()
          result.push(node.value)
          node = node.right
        }
      }
      return result
    }
    // ["a11", "a1", "b11", "b1", "b12", "a", "c11", "c1", "c12"]

> 将当前结点压入栈，然后将左子树当做当前结点，如果当前结点为空，将双亲结点取出来，将值保存进数组，然后将右子树当做当前结点，进行循环。

#### 后序遍历 ####

##### 递归遍历 #####

let bebindDFS = function(tree) { 
      let result = []
      let dfs = function(node) { 
        if (node) { 
          dfs(node.left)
          dfs(node.right)
          result.push(node.value)
        }
      }
      dfs(tree)
      return result
    }
    // ["a11", "b11", "b12", "b1", "a1", "c11", "c12", "c1", "a"]

> 先走左子树，当左子树没有孩子结点时，将此结点的值放入数组中，然后回溯遍历双亲结点的右结点，递归遍历。

##### 非递归遍历 #####

let bebindDFS = function(node) { 
      let result = []
      let stack = []
      stack.push(node)
      while(stack.length) { 
        if (node.left && !node.touched) { 
          node.touched = 'left'
          node = node.left
          stack.push(node)
          continue
        }
        if (node.right && node.touched !== 'right') { 
          node.touched = 'right'
          node = node.right
          stack.push(node)
          continue
        }
        node = stack.pop()
        node.touched && delete node.touched
        result.push(node.value)
        node = stack.length ? stack[stack.length - 1] : null
      }
      return result
    }
    // ["a11", "b11", "b12", "b1", "a1", "c11", "c12", "c1", "a"]

> 先把根结点和左树推入栈，然后取出左树，再推入右树，取出，最后取根结点。
> 
> 1.  初始化一个栈，将根节点压入栈中，并标记为当前节点(node)
> 2.  当栈为非空时，执行步骤3，否则执行结束
> 3.  如果当前节点(node)有左子树且没有被 touched，则执行4；如果当前结点有右子树，被 touched left 但没有被 touched right 则执行5 否则执行6
> 4.  对当前节点(node)标记 touched left，将当前节点的左子树赋值给当前节点(node=node.left) 并将当前节点(node)压入栈中，回到3
> 5.  对当前节点(node)标记 touched right，将当前节点的右子树赋值给当前节点(node=node.right) 并将当前节点(node)压入栈中，回到3
> 6.  清理当前节点(node)的 touched 标记，弹出栈中的一个节点并访问，然后再将栈顶节点标记为当前节点(item)，回到3

### 广度优先遍历 ###

广度优先遍历二叉树(层序遍历)是用队列来实现的，广度遍历是从二叉树的根结点开始，自上而下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

##### 递归遍历 #####

let recursionBFS = function(tree) { 
      let result = []
      // 先将要遍历的树压入栈
      let stack = [tree]
      // 记录执行到第几层
      let count = 0
      let bfs = function() { 
        let node = stack[count]
        if (node) { 
          result.push(node.value)
          if (node.left) stack.push(node.left)
          if (node.right) stack.push(node.right)
          count++
          bfs()
        }
      }
      bfs()
      return result
    }
    // ["a", "a1", "c1", "a11", "b1", "c11", "c12", "b11", "b12"]

##### 非递归算法 #####

let BFS = function(node) { 
      let result = []
      let queue = []
      queue.push(node)
      let pointer = 0
      while(pointer < queue.length) { 
        let node = queue[pointer++]
        result.push(node.value)
        node.left && queue.push(node.left)
        node.right && queue.push(node.right)
      }
      return result
    }
    // ["a", "a1", "c1", "a11", "b1", "c11", "c12", "b11", "b12"]

--------------------

## LeetCode ##

#### 102. 二叉树的层序遍历 ####

#### 104. 二叉树的最大深度 ####

> BFS，广度优先遍历。每一次用一个数组temp保存上一层的所有节点，每次计数器count+1。当temp为空的时候，也就是此时都是叶子节点情况。

#### 107. 二叉树的层序遍历 II ####

###### BFS 思路 ######

> BFS 是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用 BFS 来做非常合适。BFS 需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。

> 时间复杂度：O(n)  
> 空间复杂度：O(n)

###### DFS 思路 ######

> DFS 是沿着树的深度遍历树的节点，尽可能深地搜索树的分支

> DFS 做本题的主要问题是： DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中，在递归时要记录每个节点的深度 depth 。递归到新节点要把该节点放入 depth 对应列表的末尾。当遍历到一个新的深度 depth ，而最终结果 res 中还没有创建 depth 对应的列表时，应该在 res 中新建一个列表用来保存该 depth 的所有节点。

> 时间复杂度：O(n)  
> 空间复杂度：O(h)，h为树的高度

var levelOrderBottom = function (root) { 
      const res = [];
      let dep = function (node, depth) { 
        if (!node) return;
        res[depth] = res[depth] || [];
        res[depth].push(node.val);
        dep(node.left, depth + 1);
        dep(node.right, depth + 1);
      };
      dep(root, 0);
      return res.reverse();
    };

### 二叉树的实际应用（应用场景） ###

1.  哈夫曼编码，来源于哈夫曼树（给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树），在数据压缩上有重要应用，提高了传输的有效性，详见《信息论与编码》。
2.  海量数据并发查询，二叉树复杂度是O(K+LgN)。二叉排序树就既有链表的好处，也有数组的好处， 在处理大批量的动态的数据是比较有用。
3.  Java集合中的TreeSet和TreeMap，C++ STL中的set/multiset、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。查找最大（最小）的k个数，红黑树，红黑树中查找/删除/插入，都只需要O(logk)。
4.  B-Tree，B±Tree在文件系统中的目录应用。
5.  路由器中的路由搜索引擎。

今天你学废了吗？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDc3NzIx_size_16_color_FFFFFF_t_70_pic_center 2]

参考文章：

[js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)][js]

[百度百科][Link 1]

[二叉树的实际应用（应用场景）][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDc3NzIx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/414fd7ada5a54c8cb5f232edcece8e4f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5Y-q54uX_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20221014/566b9ebdb5d74e0a90f75b1bbd7f1540.png
[img]: /images/20221014/588dd3e9392a45e495ae372f56781e5b.png
[img 1]: /images/20221014/14f4ad33e5794e7f994220d2ebada646.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDc3NzIx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221014/a3c4ce3db55b4dc39dae057504b45291.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDc3NzIx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221014/be8b8ea62d754b0b81b4dcf5b23203bd.png
[js]: https://www.jianshu.com/p/5e9ea25a1aae
[Link 1]: https://baike.baidu.com/item/%E6%A0%91/2699484?fr=aladdin#3
[Link 2]: https://blog.csdn.net/fadbgfnbxb/article/details/88701343