各种树结构知识点总结

发表于   |   更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 3.3k | 阅读时长 ≈ 3 分钟

注: 本文的对各个概念的定义不一定采用常用的标准定义, 原因有二:

  • 常用的定义描述在百度百科上即可查到
  • 更多的是想通过自己的理解, 用简短的几个关键词语或句子, 来点明核心要点

二叉树

基本概念和性质

二叉树的定义: 二叉树中的每个节点至多有2棵子树, 并且子树有左右之分, 其次序不能任意颠倒。

二叉树的性质:

  1. 对于非空二叉树: $N_0 = N_2 +1$
  2. 在于非空二叉树, 第k层上的节点数不超过: $2^{k-1}$
  3. 高为h的二叉树, 总节点数不超过: $2^h-1$
  4. 具有N个节点的完全二叉树, 其高度为: $\lceil log_2(N+1) \rceil$ 或 $\lfloor log_2{N} \rfloor +1$
  5. 对于完全二叉树, 如果各个节点按照顺序存储(从 1 开始), 则节点之间编号具有一定关系:
    • 节点 $i$ 的父节点为 $\lfloor \frac{i}{2} \rfloor (i>1)$
    • $i$的左右子树分别为: $2i$ 和 $2i+1$ （如果$2i/2i+1 \geq N$, 则无左/右子树
  6. 给定N个节点, 能够成$h(N)$ 种不同的二叉树: $h(N)=…$
  7. 设有$i$个枝点, $I$为所有枝点的道路长度总和, $J$为叶的道路长度总和$J=I+2i$

注意: 二叉树不是度为2的树。 度为2的树至少要有3个节点, 而二叉树可以为空;度为2的树的左右子树是相对而言的, 当只有一个孩子时, 就无须分左右

满二叉树与完全二叉树

满二叉树: 除叶子节点外的所有节点均有两个子节点

完全二叉树: 最后一个不满的“满二叉树”, 最后一层所有节点集中在左边

二叉树的遍历

先根遍历: 根节点、左子树、右子树

递归实现

1
2
3
4
5
void preOrder(Tree t){
  visit(t->value); //访问根节点
  if (t->left)    preOrder(t->left); //访问左孩子
  if (t->right)    preOrder(t->right); //访问右孩子
}

非递归实现

对于任一节点, 其可看做是根节点, 因此直接访问, 访问后, 若其左孩子不为空, 则按相同规则访问其左子树, 当访问完左子树之后, 再访问其右子树:

对于任一节点P:

  1. 访问节点P, 并将P入栈
  2. 如果P的左孩子不为空, 则令P = P->left, 并转向第一步。若为空, 则将P出栈, 并令P = P->right, 然后转向第一步。
  3. 直到P为nullptr并且栈为空时, 结束循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<TreeNode*> preOrder;
if(pRoot == nullptr) return preOrder;
stack<TreeNode*> s_node;
TreeNode* P = pRoot;
while(!s_node.empty() || P!=nullptr){
  while(P!=nullptr){
    preOrder.push_back(P); // visit P
    s_node.push(P);
    P = P->left;
  }
  if(!s_node.empty()){
    P = s_node.top(); s_node.pop();
    P = P->right; // go to right child
  }
}

中根遍历: 左子树、根节点、右子树

递归

1
2
3
4
5
6
7
void in_order(TreeNode* pRoot){
  if(pRoot != nullptr){
    in_order(pRoot->left);
    visit(pRoot);
    in_order(pRoot->right);
  }
}

非递归

对于任一节点, 优先查看其左孩子, 而左孩子节点又可以看作是一个根节点, 则继续优先查看其左孩子, 直到遇到左孩子节点为空的根节点才进行访问。然后再转向查看其右孩子, 右孩子可看作是一个根节点, 继续按上面的规则循环:

对于任一节点P:

  1. 若其左孩子不为空, 则就P入栈并将P的左孩子置为当前的P, 然后继续查看当前P的左孩子, 直到为空；
  2. 经过上一步后, P指向了空的左孩子, 因此取栈顶元素并进行出栈操作, 同时访问该栈顶节点, 然后将P置为栈顶节点的右孩子（无需判断右孩子是否为空, 若为空则下一次循环会自动继续取栈顶）
  3. 知道P为nullptr并且栈为空时循环结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<TreeNode*> inOrder;
if(pRoot == nullptr) return inOrder;
stack<TreeNode*> stack_node;
TreeNode* P = pRoot;
while(!stack_node.empty() || P !=nullptr){
  while(P!=nullptr){
    stack_node.push(P);
    P = P->left;
  }
  if(!stack_node.empty()){
    P = stack_node.top(); stack_node.pop();
    inOrder.push_back(P); // visit P
    P = P->right;
}

后根遍历: 左子树、右子树、根节点

递归

1
2
3
4
5
6
7
void in_order(TreeNode* pRoot){
  if(pRoot != nullptr){
    in_order(pRoot->left);
    in_order(pRoot->right);
    visit(pRoot);
  }
}

非递归

后序遍历的非递归实现是最难的一种。因为在后序遍历中, 要保证左孩子和右孩子都已被访问, 并且左孩子在右孩子之间访问, 最后才能访问根节点。有两种思路:

思路一:
思路二:

二叉排序树（Binary Sort Tree, BST）

基本概念和性质

定义: 也叫二叉查找树或有序二叉树。当树不为空时, 该树具有如下性质:

  • 左子树上的所有节点值, 均小于其根节点的值
  • 右子树上的所有节点值, 均大于其根节点的值
  • 左、右子树也分别为二叉排序树
  • 没有键值相等的节点

性质: 对二叉排序树进行中根遍历, 即可得到一串有序数列（从小到大）

时间复杂度: 插入与查找的复杂度均为$O(logn)$, 但在最坏情况下为$O(n)$（原因在于树不一定是平衡的）

平衡二叉树

AVL树, 名字来源于其发明者 Adelson-Velsky 和 Landis

红黑树

B+树

字典树

基本概念

Trie 树, 又称字典树, 单词查找树或前缀树, 是一种用于快速检索字符串的多叉树结构, 如英文字母的字典树是一个26叉树, 数字的字典树是一个10叉树.
字典树可以利用字符串的公共前缀来节约空间, 如下图所示.

当然, 如果字符串列表中存在大量没有公共前缀的字符串, 则字典树会变得非常消耗内存. 字典树的基本性质可以概括为以下三点:

  • 除根节点以外, 每个节点都只包含一个字符(根节点不包含字符)
  • 当前节点的所表示的字符串, 就是将从根节点到当前节点的路径上的字符连接起来的字符串.
  • 每个节点的所有子节点包含的字符各不相同

基本实现

http://dongxicheng.org/structure/trietree/

高级实现