数据结构 ​

树 ​

• 根节点：树的顶部节点，没有父节点
• 子节点：树中每个节点可以有零个或多个子节点
• 叶节点：没有子节点的节点称为叶节点（Leaf Node）或终端节点
• 父节点：每个节点除了根节点外，都有一个父节点
• 路径：从根节点到任意节点的路径称为路径
• 深度（Depth）：节点的深度是指从根节点到该节点的路径的长度
• 高度（Height）：树的高度是指从根节点到叶节点的最长路径的长度
• 度（Degree）：节点拥有的子节点数量
• 带权路径长度（Weighted Path Length）：二叉树有n个带权值的叶子结点，从根节点到各个叶子结点的路径长度与相应结点权值的乘积的和

查询节点，并返回路径

function findMatchingNodes(tree, searchText) {
  const result = []

  function traverse(node, path) {
    if (node.text.includes(searchText))
      result.push({ node, path })

    if (node.children) {
      for (let i = 0; i < node.children.length; i++) {
        const child = node.children[i]
        traverse(child, [...path, { id: child.id, name: child.text }])
      }
    }
  }

  traverse(tree[0], [])

  return result
}

function findMatchingNodes(tree, searchText) {
  const result = []

  function traverse(node, path) {
    if (node.text.includes(searchText))
      result.push({ node, path })

    if (node.children) {
      for (let i = 0; i < node.children.length; i++) {
        const child = node.children[i]
        traverse(child, [...path, { id: child.id, name: child.text }])
      }
    }
  }

  traverse(tree[0], [])

  return result
}

二叉树 ​

二叉树（Binary Tree）：每个节点最多有两个子节点的树结构。子节点通常称为左子节点和右子节点

遍历方式 ​

• 前序遍历（Preorder Traversal）：按照根节点-左子树-右子树的顺序遍历二叉树 V | L | R
• 中序遍历（Inorder Traversal）：按照左子树-根节点-右子树的顺序遍历二叉树 L | V | R
• 后序遍历（Postorder Traversal）：按照左子树-右子树-根节点的顺序遍历二叉树 L | R | V

搜索方式 ​

深度优先 ​

深度优先搜索从起始节点开始，沿着一条路径尽可能深入地访问节点
按照前序、中序或后序遍历的顺序访问树的节点

广度优先 ​

广度优先搜索按照层级的顺序进行遍历，即先访问根节点，然后依次访问根节点的所有子节点，再依次访问子节点的子节点

二叉搜索树 ​

二叉树的一种特殊形式，它满足以下条件：左子节点的值小于等于当前节点的值，右子节点的值大于当前节点的值。这个特性使得二叉搜索树在查找、插入和删除操作上具有高效性，常见的二叉树有红黑树

平衡二叉树 ​

平衡二叉树（Balanced Binary Tree）：也称为自平衡二叉树，是一种特殊的二叉树，其左子树和右子树的高度差不超过1

完全二叉树 ​

除了最后一层外，其他层的节点都被填满，并且最后一层的节点从左到右连续地排列

B树 ​

一种自平衡的搜索树结构，用于存储大量数据并支持高效的查找、插入和删除操作。B树通常应用于数据库和文件系统等存储系统中

Trie树 ​

Trie树（字典树或前缀树）：一种专门用于字符串匹配和前缀搜索的树结构。Trie树的每个节点代表一个字符，从根节点到叶节点的路径表示一个字符串

线索二叉树 ​

是一种对二叉树进行改进的数据结构，旨在提高二叉树的遍历效率，除了指向左右子节点的指针之外，还添加了一些线索（Thread）指针，用于连接节点的前驱和后继节点

标志域 ​

leftTag 和 rightTag 规定
leftTag

• 0 - leftChild 域指向左孩子
• 1 - leftChild 域指向前驱
• rightTag 同理

哈夫曼树 ​

具有最小带权路径长度的二叉树称为哈夫曼树（最优树）；哈夫曼树主要用于数据压缩和编码

• 权值越大的叶子结点越靠近根节点
• 权值越小的叶子结点越远离根节点
• 左分支为0，右分支为1

计算方法 ​

1. 给定n个权值 {W1 ,W2, W3, ... Wn}, 构造n棵只有一个叶子结点的二叉树，得到一个二叉树集合F={T1 ,T2, T3, ... Tn}
2. 在F中选取根节点的权重最小的两棵二叉树，作为左、右子树构造一棵新的二叉树，新二叉树根节点权重为左、右子树之和
3. 在集合F中删除左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中
4. 重复 2、3两步，当F中只剩下一棵二叉树时，这就是哈夫曼树

8个叶子结点，权重分别为 [29, 7 ,8 ,14, 3, 5, 23, 11]

               100
           /        \
          42          52
        /    \      /    \
       19     23   29     29
     /    \             /    \
    8      11          14     15
  /    \                    /    \
 3      5                  7      8

8个叶子结点，权重分别为 [29, 7 ,8 ,14, 3, 5, 23, 11]

               100
           /        \
          42          52
        /    \      /    \
       19     23   29     29
     /    \             /    \
    8      11          14     15
  /    \                    /    \
 3      5                  7      8