树与森林

上周学习了二叉树,这是一种比较特殊的树,因为它至多只有两个孩子。而实际上,一般的树可以有多个孩子,这就使问题变得复杂了。首先要解决的是,如何表示一颗一般树?大致有双亲表示法孩子链表法孩子兄弟法三种。

树的三种表示方法

双亲表示法

顾名思义,就是给每个节点添加一个数据域,存放它的双亲的信息(说是双亲,其实只有一个)。这样的储存方法,给定一个节点,我们可以用O(1)的时间找到父亲,但却要遍历整颗树来找齐它的孩子。同时,由于没有自上而下的指针,我们至少要保存全部的叶节点,而现实中,是保存了全部的节点,并保存在一张表中。如图所示。

image-20221111223935523

孩子链表表示法

回顾二叉树的表示方法,我们是通过两个指针left和right来指示两个孩子,能否用在一般树中呢?有一个困难是:我们不知道每个节点可能有多少个孩子。所以,可以用一个vector<TreeNode*>来保存孩子指针们。不过,由于树结构可能面临频繁的增删,应该用链表代替数组,也就是list<TreeNode*>来保存孩子。如图所示。这种方法,我们只要保存根节点即可

此外,如果知道了最大分叉数,就可以直接写成数组了,比如字典树,由于一共只有26个英文字母,所以用的是Trie* children[26]储存孩子节点们。

image-20221111224644834

孩子兄弟表示法

对于树上的每一个节点,我们用一个二叉树节点代替它,将left(firstChild)指向它的第一个孩子right(nextsibling)指向它的紧邻的兄弟。通过这样的转化,我们可以将任意一颗树转化为二叉树。因此,之前对二叉树的操作又可以移植过来了。孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法,通常又被称为”二叉树表示法”或”二叉链表表示法”。如图所示

image-20221111230959421

树的遍历

树共有三种遍历方法:先根遍历后根遍历层序遍历。先根遍历是先访问根节点,然后依次从左到右访问每一棵子树;后根遍历是先依次访问每一颗子树,再访问根节点;层序遍历是从上往下、从左往右访问每一个节点。与二叉树相比,树并没有中根遍历。这是因为每个节点孩子数不确定,不好说访问几颗子树后访问根节点,所以没有定义中根遍历。

树与对应二叉树遍历的联系

先看一个例子:

image-20221112011648535

树的先根遍历:ABEKFCGDHIJ,后根遍历:KEFBGCHIJDA,层序遍历:ABCDEFGHIJK

二叉树的先序遍历:ABEKFCGDHIJ,中序遍历:KEFBGCHIJDA,后序遍历:KFEGJIHDCBA,层序遍历:ABECKFGDHIJ

可以直观地看出,树的先根遍历对应二叉树的先序遍历;树的后根遍历对应二叉树的中序遍历。下面证明之:

  • 先根遍历,树的遍历是这样进行的:先访问根节点,然后visit along first branch,并立即访问,直到找到没有子树的节点,向上找到有第二颗子树的节点,将控制权转交给它的下一棵子树,访问过后,逐级往上。而对应二叉树是这样进行的:访问根节点,然后visit along left branch,并随即访问,这相当于上面的visit along first branch,因为左孩子对应第一棵子树。直到找到没有左子树的节点,将控制权转交给它的右子树,也就是next sibling,这相当于上面的找到下一棵子树,接着逐级往上。所以先根遍历等价于先序遍历。
  • 后根遍历,树的遍历是这样进行的:visit along first branch并找到没有子树的节点,访问之,然后访问它的下一个兄弟,待所有子树访问完后,再访问父亲,逐级往上。而对应二叉树的中序遍历是这样进行的:visit along left branch直到找到没有左子树的节点,访问之,然后控制权移交给它的右子树,相当于它的下一个兄弟。待它的子孙都访问完了,访问它的父亲,然后再访问父亲的兄弟们,逐级往上。所以后根遍历等价于中序遍历。

那树的层序遍历相当于二叉树的什么呢?其实是二叉树逆时针旋转45度再进行层序遍历的结果。体现在代码上,就是对每一个节点的左孩子,visit along right branch,并将沿途节点入队即可。

森林

森林,顾名思义,就是多棵树的组合。森林也可以转化为二叉树,方法是构建一个虚拟根节点,将各棵树的根节点作为它的孩子们,形成一整棵树,接着转为二叉树,再把根节点删掉即可。

再遍历森林时,我们将它分为三部分:根节点第一棵子树其他子树。森林有两种遍历方法:先序遍历和中序遍历,它们等价于对形成的二叉树进行先序和后序遍历,这里就不证明了。

练习题

这周有两道题目,第一题是将双亲表示法表示的树转换成孩子兄弟法表示的二叉树,思路就是如果出现过兄弟了,就将当前节点作为上一个兄弟的右子树,否则作为父亲的左子树,没什么好说的。

第二道题有点意思,给定一颗用孩子兄弟法表示的树,如何求出原森林的深度?求深度,一种很直白的方法就是层序遍历,这就回到了上面那个问题,即树的层序遍历如何体现在二叉树上?上面讨论过了,这里给出代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int getDepthOfForest(TreeNode *root)
{
int depth = 0;
queue<TreeNode *> q;
while (root)//visitAlongRightBranch
{
q.push(root);
root = root->right;
}
while (!q.empty())
{
++depth;
int cnt = q.size();
for (int i = 1; i <= cnt; ++i)
{
TreeNode *node = q.front()->left;
q.pop();
while (node)//visitAlongRightBranch
{
q.push(node);
node = node->right;
}
}
}
return depth;
}

事实上,如果仅仅需要得到深度,不用这么麻烦。我们只要对二叉树进行后序遍历,向上返回从该节点开始右下方的最大深度即可,也就是孩子的深度+1与兄弟深度中较大者,也就是max(leftDepth+1,rightDepth)。代码如下:

1
2
3
4
5
6
int getDepth(TreeNode *node)
{
if (node == NULL)
return 0;
return max(getDepth(node->left) + 1, getDepth(node->right));
}