书本网 > 其他小说 > 离语 > 第327章 半

第327章 半(1 / 2)

推荐阅读: 高冷军少之独占爱妻 第五人格:我将救赎一切 轮回印 被家族放弃后,我成了宠物店主 血脉剑神 国运之战:我以神明镇诸天 女扮男装后我成了男主兄弟 山水行记 烟雨神界 生命最后三年,高冷总裁妻子疯狂报复我! 抗日小透明的自新之路 重生的夫君儿子每天都在想怎么弄死我 厨神,妖兽:不好,我们成食材了 掐指一算,你是逃犯! 陈年诡事 穿宋,我反了 一条狗的漫漫修行路 重回少年,孩子她妈成了女总裁 从得到鸿蒙珠开始修真 第四天灾,但柯学世界 师妹表白不成想要囚禁我 玄幻,从码头开启超凡之路 开在火影的便利店 我在天牢,长生不死 我是你爸 大唐:开局碰瓷长乐公主 金戈丽人行:天命之魁 村滥 重生88,从大山挖参开始! 快穿之在小世界里边苟边吃瓜 诸天无限降临世界 我杜卡雷一定会成为MVP的!! 御兽,从银月天狼开始 无限分身:诸天都有我小号 错嫁:鬼眼王妃 觉醒了异能,怎么战斗更烧脑了? 替死鬼假千金她重生了 大唐十万里 游戏入侵:我的血能毒杀异界神魔 天才与废材 当山贼开始宅斗 御兽:我能不断进化兽娘 傻大阳,求求你,弄死我吧 高武独行 僵尸校园,有亿把枪不过分吧 神奇宝贝:系统开局 符道之祖 无敌归来,未婚妻却流落风尘 重生后,四岁萌娃横扫末世! 变成龙的我,今天该干什么 此生,愿为殿下手中刃 木叶骑士王 综穿之雪色随心 大傻川,求你,弄死我吧 HP:失色魂灵 白雪皇帝,从恶魔小姐管家做起? 凡人修仙:开局看守草药场 重回七零,与病娇老公举案齐眉 重生:校花姐姐别追我 小松的爱情保卫战

设一棵二叉树有n个结点,则有n-1条边(指针连线),而n个结点共有2n个指针域

(Lchild和Rchild),显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结

点的直接前驱和直接后继信息。

为避免混淆,对结点结构加以改进,增加两个标志域,如图所示。用这种结点结构构成

的二叉树的存储结构;叫做线索链表;指向结点前驱和后继的指针叫做线索;

2、线索二叉树的构建

按照某种次序遍历,加上线索的二叉树称之为线索二叉树。线索化二叉树:二叉树的线

索化指的是依照某种遍历次序使二叉树成为线索二叉树的过程。

线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程。

【2013年】若x是后序线索二叉树中的叶结点,且x存在左兄弟结点Y,则x的右

线索指向的是______。

A.x的父结点b.以Y为根的子树的最左下结点

c.x的左兄弟结点Yd.以Y为根的子树的最右下结点

【2014年】若对如下的二叉树进行中序线索化,则结点x的左、右线索指向的结点分

别是______。

A.e、cb.e、ac.d、cd.b、a考点14:树和二叉树(★★★)

1、树转化为二叉树

对于一般的树,可以方便地转换成一棵唯一的二叉树与之对应。将树转换成二叉树在“孩

子兄弟表示法”中已给出,其详细步骤是:

1加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。

2去连线。除最左的第一个子结点外,父结点与所有其它子结点的连线都去掉。

3旋转。将树顺时针旋转450,原有的实线左斜。

4整型。将旋转后树中的所有虚线改为实线,并向右斜。

这样转换后的二叉树的特点是:

◆二叉树的根结点没有右子树,只有左子树;

◆左子结点仍然是原来树中相应结点的左子结点,而所有沿右链往下的右子结点均是原来

树中该结点的兄弟结点。

由于二叉树和树都可用二叉链表作为存储结构,对比各自的结点结构可以看出,以二叉

链表作为媒介可以导出树和二叉树之间的一个对应关系。

◆从物理结构来看,树和二叉树的二叉链表是相同的,只是对指针的逻辑解释不同而已。

◆从树的二叉链表表示的定义可知,任何一棵和树对应的二叉树,其右子树一定为空。

2、二叉树转换成树

对于一棵转换后的二叉树,如何还原成原来的树?其步骤是:

(1)加虚线。若某结点i是其父结点的左子树的根结点,则将该结点i的右子结点以及沿右

子链不断地搜索所有的右子结点,将所有这些右子结点与i结点的父结点之间加虚线相连,

如图(a)所示。

(2)去连线。去掉二叉树中所有父结点与其右子结点之间的连线,如图(b)所示。

(3)规整化。将图中各结点按层次排列且将所有的虚线变成实线,如图(c)所示。

3、森林转换成二叉树

转换步骤:

1将F={t1,t2,?,tn}中的每棵树转换成二叉树。

2按给出的森林中树的次序,从最后一棵二叉树开始,每棵二叉树作为前一棵二叉树的

根结点的右子树,依次类推,则第一棵树的根结点就是转换后生成的二叉树的根结点,如图

所示。

4、二叉树转换成森林

最新小说: 小马宝莉之我为谋士 80军婚狠狠宠 又宠又撩,豪门教官我不要了 成亲当天,老婆被人拐跑了? 重生1979,身边躺着女知青 情深不悔:顾总的心尖宠 殊晏 以白狐游戏人间 小师祖真不浪,她只是想搞钱 致命游戏:归梦 乱讲!爱妃秉性纯良怎会是坏女人 苦海尽头 精分太离谱!我角色切换自如 黄泉碧落皆不见 神渊世纪续上 四合院:暴躁街溜子,人狠话又多 娇生柔情 解婚约和求婚的,竟然是同一人! 幼儿园带娃日常 斩神:代理六颗宝石,弹指灭神 人在90,脚踹渣男,卖饼致富 龙吟变 穿书之我的路人修仙之路 凤命凰谋 穿越时空:白领在古代的 快穿:大佬的养老生活 大唐神医孙思邈 异时空:彼端魔法少女 穿越带空间商城老李家开挂了 契约!墨爷竟被金丝雀偷了心 仙途逆世风云 校草校花奇遇记 不可名状的养成游戏 爱你如星光璀璨 修真高手在异界 假面帝骑:总裁,你想和谁谈恋爱 重生七零:真千金吃瓜摆烂当学霸 快穿我的超市绑定了位面交易系统 高校里最恐怖的班级 诡道,这个世界太疯癫 重生十五99天后当包租婆考清北 斩神入仙逆:万魂幡里做兄弟 最后的道子 四合院:61开局,我是天才 撩心撩情:冷宫皇后想复仇! 穿越之后才知道美食可以致富 灵犀恋梦:都市奇幻情长 染指浮华 约战中的假面骑士 快穿之炮灰只想修炼 重生嫡嫁,第一奸臣他为我折了腰 南者煞 重生之一个也跑不掉 灵脉少年 重生后我总在失忆 庶女嫡宫 百年诸神 你也没说穿的都是一个世界啊 错爱成殇:复仇之恋 人在泰拉开事务所