树的相关算法以及树转换为二叉树

树的相关概念

二叉树 Binary Tree

每个节点可有左右区分的两个子节点(子树)；节点的值可能相同(代码中不能根据值判断是否为同一个节点)；

完全二叉树

二叉树的基础上，树的每一行都是满的(2^(k-1)个节点在第k行)，除了最后一行。最后一行的节点从左到右是满的。

满二叉树

二叉树的基础上，树的每一行都是满的(2^(k-1)个节点在第k行)。

二叉排序树 Binary Search Tree (BST)

在二叉树的基础上，本节点的值必定大于左子树，小于右子树；所有节点的值都不相同；

问题：如何判断一棵树是BST？

1. 每个节点至多有两个子节点；
2. 每个节点的值必须大于/小于父节点，同时大于/小于父父节点

平衡二叉树 Balanced Binary Tree 或 AVL树

在二叉排序树的基础上，每个节点左右两个子树的高度差不超过1。

• 保证插入、删除以及查找节点的时间最好和最坏都在log(n)
• 避免BST树可能退化为链表的可能
• 带来的代价是维持平衡需要的额外旋转log(n)时间
• 可以为空树

前缀树 Prefix Tree 或者 Trie Tree

根节点为空，每个字母是一个节点（如26个小写字母），每个节点的子节点同样是。从头到尾会组成一个单词。一棵排序树。

具有的特性：

• 快速判断某个单词是否存在于一堆单词中；O(LengthofWord)
• 获得以某个前缀开始的单词的数量；
• 占用内存较大（每个节点要保存26个指针）；
• 每个节点包含以下元素
  • 当前字符；
  • 以当前字符结尾的单词个数；
  • 以当前字符为前缀的单词个数；
  • 指向子节点的指针数组；

与Hash的异同：

• 前缀树较常应用于普通长度的单词（单词长度），对于MD5等较长的无规则字符不太好；
• Hash在工业中更为常用方便，处理大量数据；

区间树 Segment Tree

属于二叉搜索树，每个节点代表一段范围。用于快速求解随机范围内值的和。更新具体节点的值的花费是O(logn)。

区间树

红黑树与AVL树

STL中set、map、multiset、multimap是由红黑树实现的，所以查找速度是O(log(n))

STL中unordered_set、unordered_map、unordered_multiset、unordered_multimap是由hash实现的，所以查找速度是O(1)

相同点

• 两者均为（自）平衡二叉树的实现算法
• 插入、删除、查找的算法复杂度相同（红黑树），都是O(log(n))

不同点

• AVL树严格维持左右子树高度差在1之内（严格平衡树），而红黑树并不严格遵守（相对便宜的解决方案）
• 红黑树插入和删除效率较高（统计性能比AVL好）
• 红黑树的检索效率不如AVL树
• 红黑树的根节点是黑的

红黑树或者AVL树与哈希的选取

红黑树相对于哈希表，在选择使用的时候有什么依据？

权衡三个因素: 查找速度, 数据量, 内存使用，可扩展性。

• 查找速度：哈希更优
• 数据量与内存：哈希消耗更大
• 可扩展性：哈希更不易扩展，适应于静态数据

参考资料：

• 搞定面试中的红黑树问题
• 红黑树和AVL树的比较
• 红黑树 VS AVL树
• 平衡二叉树（解惑

B树

多路树

树转换为二叉树

很简单，每个节点的最左边的儿子还是儿子，其他儿子变成这个儿子的孙子、曾孙子等，可以递归进行：

struct Node
{
  int val;
  int childrenNum;
  Node** children;
  void addChild(Node* n)
  {
    children[childrenNum++] = n;
  }
};

void transfer(Node* root)
{
  if (root == NULL)
    return;

  for (int i = 0; i < root->childrenNum; i++)
  {
    transfer(root->children[i]); // 注意：必须先执行子节点的变换
    if (i != 0)
      root->children[i - 1]->addChild(root->children[i]);
  }

  root->childrenNum = root->childrenNum == 0 ? 0 : 1;
}

树的其他常见算法

最低公共祖先节点 Lowest Common Ancesters (LCA)

排序二叉树

在二叉排序树中，如果两个节点的某个公共父节点的值在两个节点值之间，那么这个节点必然是两个节点的最低公共祖先。

也就是说，在两个节点的所有公共祖先节点中，只有最低公共祖先节点的值在两者之间。

利用这个结论，可以快速的在BST(Binary Search Tree)中找到两个节点值p与q的LCA(p < q)。

while (node)
{
  if (p < node->val && q < node->val)
  {
    node = node->left;
    continue;
  }
  if (p > node->val && q > node->val)
  {
    node = node->right;
    continue;
  }

  if (p < node->val && q > node->val)
    return node; // 找到LCA
}

普通二叉树

首先，在普通二叉树中没有二叉搜索树的规律，因此可以使用递归进行运算。

通常情况下我们会构造递归函数，目的是返回子树中p与q的LCA，否则返回NULL。

但问题来了，如果节点左右子节点都为NULL，如何判断当前节点是否是p与q的LCA？

所以可以让递归函数返回子树中是否包含p与q，那么就可以判断出当前节点是否是LCA了。

TreeNode* lowestCommonAncestorHelper(TreeNode* root, TreeNode* p, TreeNode* q, bool & cp, bool & cq) {
    if (root == NULL)
    {
        cp = false;
        cq = false;
        return NULL;
    }

    bool lcp(false), lcq(false), rcp(false), rcq(false);
    TreeNode* ln = lowestCommonAncestorHelper(root->left, p, q, lcp, lcq);
    if (lcp && lcq)
    {
        cp = true;
        cq = true;
        return ln;
    }
    TreeNode* rn = lowestCommonAncestorHelper(root->right, p, q, rcp, rcq);
    if (rcp && rcq)
    {
        cp = true;
        cq = true;
        return rn;
    }

    cp = lcp || rcp || (root == p); // 注意：！普通的二叉树可能不是二叉搜索树(BST)，所以树节点的值可能重复
    cq = lcq || rcq || (root == q);
    if ( cp && cq )
        return root;

    return NULL;
}

树的左右对称交换

使用递归，左右交换即可。

void reverse(Node * root)
{
  if (root == NULL)
    return;

  swap(root->left, root->right); // swap和下面reverse的顺序可以调换
  reverse(root->left);
  reverse(root->right);
}

类似题目

对称交换二进制

使用二分法左右交换。

void inverseBinary(int &bin)
{
	bin = ((0x0000FFFF & bin) << 16) | ( (0xFFFF0000 & bin) >> 16);
	bin = ((0x00FF00FF & bin) << 8 ) | ( (0xFF00FF00 & bin) >> 8);
	bin = ((0x0F0F0F0F & bin) << 4 ) | ( (0xF0F0F0F0 & bin) >> 4);
	bin = ((0x33333333 & bin) << 2 ) | ( (0xCCCCCCCC & bin) >> 2);
	bin = ((0x55555555 & bin) << 1 ) | ( (0xAAAAAAAA & bin) >> 1);
}

对称交换字符串

使用左右两个指针中间移动交换即可。

深度优先搜索(DFS)与广度优先搜索(BFS)

深度优先搜索使用Stack递归即可，而广度优先搜索需要使用队列(deque).

参考资料

• WIKI二元搜尋樹