考研专业课之统考计算机蓝宝书(21)
3.2.4 线索二叉树
1. 线索二叉树的定义
按照某种遍历方式对二叉树进行遍历,可以把二叉树中所有结点排列为一个线性序列。在该序列中,除第一个结点外,每个结点有且仅有一个直接前驱结点;除最后一个结点外,每个结点有且仅有一个直接后继结点。但是,二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么,二叉树的存储结构中并没有反映出来,只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息,可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索(thread),加了线索的二叉树称为线索二叉树。
2. 线索二叉树基本操作的实现
(1). 建立一棵中序线索二叉树
建立线索二叉树,或者说对二叉树线索化,实质上就是遍历一棵二叉树。在遍历过程中,访问结点的操作是检查当前结点的左、右指针域是否为空,如果为空,将它们改为指向前驱结点或后继结点的线索。为实现这一过程,设指针pre始终指向刚刚访问过的结点,即若指针p指向当前结点,则pre指向它的前驱,以便增设线索。
另外,在对一棵二叉树加线索时,必须首先申请一个头结点,建立头结点与二叉树的根结点的指向关系,对二叉树线索化后,还需建立最后一个结点与头结点之间的线索。
下面是建立中序线索二叉树的递归算法,其中pre为全局变量。
(2). 在中序线索二叉树上查找任意结点的中序前驱结点
对于中序线索二叉树上的任一结点,寻找其中序的前驱结点,有以下两种情况:
1. 如果该结点的左标志为1,那么其左指针域所指向的结点便是它的前驱
结点;
2. 如果该结点的左标志为0,表明该结点有左孩子,根据中序遍历的定义,
它的前驱结点是以该结点的左孩子为根结点的子树的最右结点,即沿着其左子树的右指针链向下查找,当某结点的右标志为1时,它就是所要找的前驱结点。
在中序线索二叉树上寻找结点p的中序前驱结点的算法如下:
(3). 在中序线索二叉树上查找任意结点的中序后继结点
对于中序线索二叉树上的任一结点,寻找其中序的后继结点,有以下两种情况:
1. 如果该结点的右标志为1,那么其右指针域所指向的结点便是它的后继
结点;
2. 如果该结点的右标志为0,表明该结点有右孩子,根据中序遍历的定义,
它的前驱结点是以该结点的右孩子为根结点的子树的最左结点,即沿着其右子树的左指针链向下查找,当某结点的左标志为1时,它就是所要找的后继结点。
在中序线索二叉树上寻找结点p的中序后继结点的算法如下:
以上给出的仅是在中序线索二叉树中寻找某结点的前驱结点和后继结点的算法。在前序线索二叉树中寻找结点的后继结点以及在后序线索二叉树中寻找结点的前驱结点可以采用同样的方法分析和实现。在此就不再讨论了。
>" 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:掠夺狂爱》是由石井隆执导,竹中直人、佐藤宽子等领衔主演日本惊悚情色电影。该片讲述了主人公红次郎替年轻女孩加藤怜寻找叫“多绘”的救命恩人,结果踏入充满危机的“粉红”漩涡中。
- 秒变单身狗:哪些话不能对恋人说
恋爱初期总是美好而甜蜜的,然而两人长期处下来,就会发现对方的不足之处。生气起来口不择言,结果深深的伤害到两人的感情。这期给大家介绍一些对恋人可不能说的一些话。
- 日本礼仪:你真的会斟酒吗?
走进社会,我们不仅要在工作上努力努力再努力,还要一边学习一些社交礼仪。酒会作为一种常见的社交活动,学会其中的斟酒礼仪也是一门学问。今日,小编给大家整理了日本的斟酒礼仪供大家参考学习。
- 汉字词和成语 - 속담_뜻이 비슷한 속담
가재는 게와 생김새가 비슷하기 때문에 게 편을 든다는 말로, 서로 인연이 있는 것끼리 한편이 된다는 뜻이다. 비슷한 속담으로 '초록은 동색', … 가재는 게와 생김새가 비슷하기 때문에 게 ...