考研专业课之统考计算机蓝宝书(25)
3.3.2 树、森林与二叉树的转换
1. 树转换为二叉树
将一棵树转换为二叉树的方法是:
(1). 树中所有相邻兄弟之间加一条连线。
(2). 对树中的每个结点,只保留它与第一个孩子结点之间的连线,删去它与
其它孩子结点之间的连线。
(3). 以树的根结点为轴心,将整棵树顺时针转动一定的角度,使之结构层次
分明。可以证明,树作这样的转换所构成的二叉树是唯一的。由上面的转换可以看出,在二叉树中,左分支上的各结点在原来的树中是父子关系,而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟,所以变换后的二叉树的根结点的右孩子必为空。事实上,一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。
2. 森林转换为二叉树
由森林的概念可知,森林是若干棵树的集合,只要将森林中各棵树的根视为兄弟,每棵树又可以用二叉树表示,这样,森林也同样可以用二叉树表示。
森林转换为二叉树的方法如下:
(1). 将森林中的每棵树转换成相应的二叉树。
(2). 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结
点作为前一棵二叉树根结点的右孩子,当所有二叉树连起来后,此时所得到的二叉树就是由森林转换得到的二叉树。
这一方法可形式化描述为:
如果F={ T1,T2,...,Tm }是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。
(1). 若F为空,即m=0,则B为空树;
(2). 若F非空,即m≠0,则B的根root即为森林中第一棵树的根Root(T1);
B的左子树LB是从T1中根结点的子树森林F1={ T11,T12,...,T1m1 }转换而成的二叉树;其右子树RB是从森林F'={ T2,T3,...,Tm }转换而成的二叉树。
3. 二叉树转换为树和森林
树和森林都可以转换为二叉树,二者不同的是树转换成的二叉树,其根结点无右分支,而森林转换后的二叉树,其根结点有右分支。显然这一转换过程是可逆的,即可以依据二叉树的根结点有无右分支,将一棵二叉树还原为树或森林,具体方法如下:
(1). 若某结点是其双亲的左孩子,则把该结点的右孩子、右孩子的右孩子......
都与该结点的双亲结点用线连起来;
(2). 删去原二叉树中所有的双亲结点与右孩子结点的连线;
(3). 整理由(1)、(2)两步所得到的树或森林,使之结构层次分明。
这一方法可形式化描述为:
如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F={ T1,T2,...,Tm }。
(1). 若B为空,则F为空;
(2). 若B非空,则森林中第一棵树T1的根ROOT(T1)即为B的根root;
T1中根结点的子树森林F1是由B的左子树LB转换而成的森林;F中除T1之外其余树组成的森林F'={ T2,T3,...,Tm }是由B的右子树RB转换而成的森林。
>" src="http://i1.w.hjfile.cn/doc/200811/32502.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/32502.gif">>" src="http://i1.w.hjfile.cn/doc/200811/26508.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/26508.gif">>" src="http://i1.w.hjfile.cn/doc/200811/52955.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/52955.gif">>" src="http://i1.w.hjfile.cn/doc/200811/71602.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/71602.gif">>" src="http://i1.w.hjfile.cn/doc/200811/11087.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/11087.gif">
猜你喜欢
- 出国留学中介前十名介绍 沪江是最好的选择
想要出国留学却没有时间没有精力去办理出国留学的手续,这个时候寻找一个好的出国留学中介就成了最好的办法,好的中介可以让自己更合理的去挑选自己喜欢的国家和学校,而且中介还有出国培训相关的内容,这...
- 日本动漫游戏:学校的圣域
feng社第9作第1弹《彼女のセイイキ(她的圣域)》,而系列的第2弹《妹的圣域》已于2015年08月28日发售,系列第3弹《学校的圣域》在2016年11月发售。
- 日本惊悚恐怖电影《裸体之夜:掠夺狂爱》
《裸体之夜2:掠夺狂爱》是由石井隆执导,竹中直人、佐藤宽子等领衔主演日本惊悚情色电影。该片讲述了主人公红次郎替年轻女孩加藤怜寻找叫“多绘”的救命恩人,结果踏入充满危机的“粉红”漩涡中。
- 秒变单身狗:哪些话不能对恋人说
恋爱初期总是美好而甜蜜的,然而两人长期处下来,就会发现对方的不足之处。生气起来口不择言,结果深深的伤害到两人的感情。这期给大家介绍一些对恋人可不能说的一些话。
- 日本礼仪:你真的会斟酒吗?
走进社会,我们不仅要在工作上努力努力再努力,还要一边学习一些社交礼仪。酒会作为一种常见的社交活动,学会其中的斟酒礼仪也是一门学问。今日,小编给大家整理了日本的斟酒礼仪供大家参考学习。
- 汉字词和成语 - 속담_뜻이 비슷한 속담
가재는 게와 생김새가 비슷하기 때문에 게 편을 든다는 말로, 서로 인연이 있는 것끼리 한편이 된다는 뜻이다. 비슷한 속담으로 '초록은 동색', … 가재는 게와 생김새가 비슷하기 때문에 게 ...