企业官网建设流程全解析

目录

按结构特征分类

普通二叉树

满二叉树（Full Binary Tree）

完美二叉树（Perfect Binary Tree）

完全二叉树（Complete Binary Tree）

斜二叉树（Skewed Binary Tree）

退化二叉树（Degenerate Tree）

按节点值规律分类

二叉搜索树（BST）

平衡二叉树（AVL树）

红黑树（Red-Black Tree）

二叉堆（Heap）

哈夫曼树（最优二叉树）

特殊用途二叉树

线索二叉树（Threaded Binary Tree）

伸展树（Splay Tree）

Treap（树堆）

线段树（Segment Tree）

树状数组（Fenwick Tree / BIT）

多叉树（非严格二叉树，但常一起考）

B树（B-Tree）

B+树（B+ Tree）

Trie（字典树/前缀树）

速查对比表

软考真题

题目

官方解析

按结构特征分类

普通二叉树

无任何特殊约束，每个节点最多2个孩子。

1 / \ 2 3 / \ 4 5

满二叉树（Full Binary Tree）

每个节点要么0个孩子，要么2个孩子，不存在度为1的节点。

1 / \ 2 3 / \ / \ 4 5 6 7

完美二叉树（Perfect Binary Tree）

所有内部节点都有2个孩子，且所有叶子在同一层。深度为k时，节点数 = 2^k - 1。

1 / \ 2 3 / \ / \ 4 5 6 7

💡 完美二叉树同时满足满二叉树和完全二叉树的定义，是最"饱满"的形态。

完全二叉树（Complete Binary Tree）

除最后一层外全满，最后一层节点从左到右连续排列。

1 / \ 2 3 / \ / 4 5 6

堆（Heap）的底层结构就是完全二叉树，可以用数组高效存储。

斜二叉树（Skewed Binary Tree）

所有节点只有左孩子（左斜）或只有右孩子（右斜），退化成链表，性能 O(n)。

左斜树 右斜树 1 1 / \ 2 2 / \ 3 3

退化二叉树（Degenerate Tree）

每个内部节点只有一个孩子（不区分左右），性能等同于链表。

1 \ 2 / 3 \ 4

按节点值规律分类

二叉搜索树（BST）

左子树所有值 < 根 < 右子树所有值，中序遍历得到有序序列。

8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13

⚠️ 极端情况下会退化成链表（如按顺序插入1,2,3,4,5），查找变成 O(n)。

平衡二叉树（AVL树）

在BST基础上，任意节点左右子树高度差 ≤ 1，通过旋转维持平衡。

8 / \ 4 12 / \ / \ 2 6 10 14

查找、插入、删除稳定 O(log n)，但旋转维护成本较高，适合读多写少场景。

红黑树（Red-Black Tree）

自平衡BST，通过红/黑着色 + 旋转规则维持近似平衡，平衡条件比AVL宽松。

8(B) / \ 4(R) 12(R) / \ / \ 2(B) 6(B) 10(B) 14(B)

五条核心规则：

• 根节点是黑色
• 红色节点的子节点必须是黑色（不能有相邻红节点）
• 从任一节点到其所有后代叶子的路径上，黑色节点数相同
• 叶子节点（NIL）是黑色
• 新插入节点默认为红色

工程中最常用！Java的HashMap/TreeMap、C++的map、Linux内核进程调度都用它。相比AVL树，插入/删除时旋转次数更少。

二叉堆（Heap）

完全二叉树 + 堆序性，分大顶堆和小顶堆。

大顶堆（父 ≥ 子） 小顶堆（父 ≤ 子） 9 1 / \ / \ 7 8 3 2 / \ / / \ / 4 5 6 4 5 6

优先队列、堆排序的底层结构。

哈夫曼树（最优二叉树）

带权路径长度（WPL）最短的二叉树，权值越大离根越近。

100 / \ 40 60 / \ 25 35

数据压缩（ZIP、JPEG）的核心算法。

特殊用途二叉树

线索二叉树（Threaded Binary Tree）

利用叶子节点的空指针，存储前驱/后继信息，省去递归或栈的开销。

普通二叉树 中序线索二叉树 A A / \ / \ B C B → C / ↑ ↓ D D ← (null)

空指针被"线索化"，遍历时无需额外空间。

伸展树（Splay Tree）

每次访问的节点通过旋转被"提升"到根位置，最近访问的节点下次查找最快。

访问节点3后，3被旋转到根： 3 / \ 1 5 \ \ 2 7

适合有局部性特征的访问模式（如缓存）。

Treap（树堆）

BST + Heap 的混合体：key满足BST性质，priority满足堆性质。

key: BST序 priority: 大顶堆 5(10) / \ 3(7) 8(5) / \ 1(3) 4(2)

通过随机priority实现期望平衡，实现简单，无需复杂旋转规则。

线段树（Segment Tree）

每个节点代表一个区间，用于高效处理区间查询（如区间求和、区间最值）。

数组: [1, 3, 5, 7] [0,3] sum=16 / \ [0,1] sum=4 [2,3] sum=12 / \ / \ [0,0] [1,1] [2,2] [3,3] 1 3 5 7

竞赛和工程中处理区间问题的利器，查询和更新均为 O(log n)。

树状数组（Fenwick Tree / BIT）

用数组模拟树结构，高效计算前缀和与单点更新。

逻辑结构（节点i管理区间长度 = lowbit(i)）： 8 / 4 / \ 2 6 / \ / \ 1 3 5 7

代码极短（核心操作仅几行），适合前缀和/区间和问题。

多叉树（非严格二叉树，但常一起考）

B树（B-Tree）

每个节点可以有多个key和多个孩子，专为磁盘存储设计，树很矮。

[17 | 35] / | \ [5|13] [21|29] [40|50]

数据库索引、文件系统的底层结构。

B+树（B+ Tree）

B树的变体，所有数据只存在叶子节点，叶子之间用链表相连。

[17 | 35] ← 内部节点只存索引 / | \ [5|13] [21|29] [40|50] ← 叶子节点存实际数据 ↓ ↓ ↓ → → → → → → → → → → → ← 叶子链表，方便范围查询

MySQL InnoDB索引就是B+树，范围查询效率极高。

Trie（字典树/前缀树）

每个节点代表一个字符，路径表示一个字符串。

root / | \ a b c / | \ p a a / \ | | p e t t | | l | (cat, bat, apple, app)

自动补全、拼写检查、IP路由。

速查对比表

软考真题

题目

解析：

画图以后，如下

官方解析

以上就是本篇文章的全部内容，喜欢的话可以留个免费的关注呦~~~