数据结构与算法Week9——树与森林
树与森林
上周学习了二叉树,这是一种比较特殊的树,因为它至多只有两个孩子。而实际上,一般的树可以有多个孩子,这就使问题变得复杂了。首先要解决的是,如何表示一颗一般树?大致有双亲表示法、孩子链表法、孩子兄弟法三种。
树的三种表示方法
双亲表示法
顾名思义,就是给每个节点添加一个数据域,存放它的双亲的信息(说是双亲,其实只有一个)。这样的储存方法,给定一个节点,我们可以用O(1)
的时间找到父亲,但却要遍历整颗树来找齐它的孩子。同时,由于没有自上而下的指针,我们至少要保存全部的叶节点,而现实中,是保存了全部的节点,并保存在一张表中。如图所示。
孩子链表表示法
回顾二叉树的表示方法,我们是通过两个指针left和right来指示两个孩子,能否用在一般树中呢?有一个困难是:我们不知道每个节点可能有多少个孩子。所以,可以用一个vector<TreeNode*>
来保存孩子指针们。不过,由于树结构可能面临频繁的增删,应该用链表代替数组,也就是list<TreeNode*>
来保存孩子。如图所示。这种方法,我们只要保存根节点即可。
此外,如果知道了最大分叉数,就可以直接写成数组了,比如字典树,由于一共只有26个英文字母,所以用的是Trie* children[26]
储存孩子节点们。
孩子兄弟表示法
对于树上的每一个节点,我们用一个二叉树节点代替它,将left(firstChild)
指向它的第一个孩子,right(nextsibling)
指向它的紧邻的兄弟。通过这样的转化,我们可以将任意一颗树转化为二叉树。因此,之前对二叉树的操作又可以移植过来了。孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法,通常又被称为”二叉树表示法”或”二叉链表表示法”。如图所示
树的遍历
树共有三种遍历方法:先根遍历、后根遍历和层序遍历。先根遍历是先访问根节点,然后依次从左到右访问每一棵子树;后根遍历是先依次访问每一颗子树,再访问根节点;层序遍历是从上往下、从左往右访问每一个节点。与二叉树相比,树并没有中根遍历。这是因为每个节点孩子数不确定,不好说访问几颗子树后访问根节点,所以没有定义中根遍历。
树与对应二叉树遍历的联系
先看一个例子:
树的先根遍历: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 | int getDepthOfForest(TreeNode *root) |
事实上,如果仅仅需要得到深度,不用这么麻烦。我们只要对二叉树进行后序遍历,向上返回从该节点开始右下方的最大深度即可,也就是孩子的深度+1与兄弟深度中较大者,也就是max(leftDepth+1,rightDepth)
。代码如下:
1 | int getDepth(TreeNode *node) |