分享
 
 
 

C++数据结构学习:二叉树(2)

王朝c/c++·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

线索化二叉树

这是数据结构课程里第一个碰到的难点,不知道你是不是这样看,反正我当初是费了不少脑细胞——当然,恼人的矩阵压缩和相关的加法乘法运算不在考虑之列。

我费了不少脑细胞是因为思考:他们干什么呢?很欣喜的看到在这本黄皮书上,这章被打了*号,虽然我不确定作者是不是跟我一个想法——线索化二叉树在现在的PC上是毫无用处的!——不知我做了这个结论是不是会被人骂死,^_^。

为了证实这个结论,我们来看看线索化二叉树提出的缘由:第一,我们想用比较少的时间,寻找二叉树某一个遍历线性序列的前驱或者后继。当然,这样的操作很频繁的时候,做这方面的改善才是有意义的。第二,二叉树的叶子节点还有两个指针域没有用,可以节省内存。说真的,提出线索化二叉树这样的构思真的很精巧,完全做到了“废物利用”——这个人真应该投身环保事业。但在计算机这个死板的东西身上,人们的精巧构思往往都是不能实现的——为了速度,计算机的各个部件都是整洁划一的,而构思的精巧往往都是建立在组成的复杂上的。

我们来看看线索化二叉树究竟能不能达到上面的两个目标。

求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继,但是前驱需要求双亲;中序线索化前驱和后继都不需要求双亲,但是都不很直接;后序线索化能依次找到前驱,但是后继需要求双亲。可以看出,线索化成中序是最佳的选择,基本上算是达到了要求。

节省内存。添加了两个标志位,问题是这两个位怎么储存?即使是在支持位存储的CPU上,也是不能拿位存储器来存的,第一是因为结构体成员的地址是在一起的,第二是位存储器的数目是有限的。因此,最少需要1个字节来储存这两个标志位。而为了速度和移植,一般来说,内存是要对齐的,实际上根本就没节省内存!然而,当这个空间用来储存双亲指针时,带来的方便绝对不是线索化所能比拟的,前面已经给出了无栈的非递归遍历。并且,在线索化二叉树上插入删除操作附加的代价太大。

综上,线索化最好是中序线索化(前序后序线索化后还得用栈,何必要线索化呢),附加的标志域空间至少1个字节,在32位的CPU会要求对齐到4字节,还不如存储一个双亲指针,同样能达到中序线索化的目的,并且能带来其他的好处。所以,线索化二叉树在现在的PC上是毫无用处的!

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

由于对其他体系不太了解,以下观点姑妄听之。在内存空间非常充裕的现在,一个节点省2~3个字节实在是没什么意思(实际上由于对齐还省不出来);而在内存非常宝贵的地方(比如单片机),会尽量避免使用树结构——利用其他的方法。所以,现在看来,线索化二叉树真的是毫无用处了。

二叉搜索树

这恐怕是二叉树最重要的一个应用了。它的构想实际是个很自然的事情——查找值比当前节点小转左,大转右,等则查到,到头了就是没找着。越自然的东西越好理解,也就越不需要我废话。在给出BST的实现之前,我们要在二叉树的类中添加一个打印树状结构的成员函数,这样,就能清楚的看出插入和删除过程。

public:

voidPRint()

{

queue*a;queueflag;ofstreamoutfile("out.txt");

BTNode*p=root;BTNodezero;boolv=true;

inti=1,level=0,h=height();

while(i

{

if(i==1

{

cout

if(v)cout

elsecout

}

else

{

cout

if(v)cout

elsecout

}

if(p-left){a.push(p-left);flag.push(true);}

else{a.push(&zero);flag.push(false);}

if(p-right){a.push(p-right);flag.push(true);}

else{a.push(&zero);flag.push(false);}

p=a.front();a.pop();v=flag.front();flag.pop();i++;

}

cout

}

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

打印树状结构的核心是按层次遍历二叉树,但是,二叉树有许多节点缺左或右子树,连带的越到下面空隙越大。

为了按照树的结构打印,必须把二叉树补成完全二叉树,这样下面的节点就知道放在什么位置了——a.push(&zero);但是这样的节点不能让它打印出来,所以对应每个节点,有一个是否打印的标志,按理说pair结构很合适,为了简单我用了并列的两个队列,一个放节点指针——a,一个放打印标志——flag。这样一来,循环结束的标志就不能是队列空——永远都不可能空,碰到NULL就补一个节点——而是变成了到了满二叉树的最后一个节点2^(height+1)-1。——黄皮书对于树高的定义是,空树为的高度为-1。

对于输出格式,注重的是到了第1、2、4、8号节点要换行,并且在同一行中,第一个节点的域宽是后序节点的一半。上面的函数在树的层次少于等于5(height

二叉搜索树的实现

实际上就是在二叉树的基础上增加了插入、删除、查找。

#include"BaseTree.h"

template

classBSTree:publicBTree

{

public:

BTNode*&find(constT&data)

{

BTNode**p=&root;current=NULL;

while(*p)

{

if((*p)-data==data)break;

if((*p)-dataright);}

else{current=*p;p=&((*p)-left);}

}

return*p;

}

boolinsert(constT&data)

{

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

BTNode*&p=find(data);if(p)returnfalse;

p=newBTNode(data,NULL,NULL,current);returntrue;

}

boolremove(constT&data)

{

returnremove(find(data));

}

private:

boolremove(BTNode*&p)

{

if(!p)returnfalse;BTNode*t=p;

if(!p-left!p-right)

{

if(!p-left)p=p-right;elsep=p-left;

if(p)p-parent=current;

deletet;returntrue;

}

t=p-right;while(t-left)t=t-left;p-data=t-data;current=t-parent;

returnremove(current-left==t?current-left:current-right);

}

};

以上代码有点费解,有必要说明一下——非线性链式结构操作的实现都是很让人费神。insert和remove都是以find为基础的,因此必须让find能最大限度的被这两个操作利用。

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

对于insert,需要修改查找失败时的指针内容,显然这是个内部指针(在双亲节点的内部,而不是象root和current那样在节点外面指向节点),这就要求find返回一个内部指针的引用。但是C++的引用绑定到一个对象之后,就不能再改变了,因此在find内部的实现是一个二重指针。insert操作还需要修改插入的新节点的parent指针域,因此在find中要产生一个能被insert访问的指向find返回值所在节点的指针,这里用的是current。实际上find返回的指针引用不是current-left就是current-right。这样一来,insert的实现就非常简单了。

对于remove,需要修改查找成功时的指针内容,同样是个内部指针。在find的基础上,很轻易就能得到这个内部指针的引用(BTNode*&p=find(data)。

在p-left和p-right中至少有一个为NULL的情况下,假如p-left==NULL,那么就重连右子树p=p-right,反之,重连左子树p=p-left。注重,左右子树全空的情况也包含在这两个操作中了——在p-left==NULL的时候重连右子树,而这时p-right也是NULL——因此不必列出来。假如重连后p不为空,需要修改p-parent=current。

若p-left和p-right都不为空,可以转化为有一个为空。例如一个中序有序序列[1,2,3,4,5],假设3既有左子树又有右子树,那么它的前驱2一定缺右子树,后继4一定缺少左子树。【注1】这样一来删除节点3就等效成从[1,2,3(4),4,5]删除节点4。这样就可以利用上面的在p-left和p-right中至少有一个为NULL的情况下的方法了。还是由于C++的引用不能改变绑定对象,这里是用利用递归来解决的,还好最多只递归一次。假如用二重指针又是满天星星了,这就是明明是尾递归却没有消去的原因。

【注1】这是因为,假如3既有左子树又有右子树,那么2一定在3的左子树上,4一定在3的右子树上;假如2有右子树,那么在2和3之间还应该有一个节点;假如4有左子树,那么3和4之间也应该还有一个节点。

【闲话】上面关于remove操作p-left和p-right都不为空的处理方法的讲解,源于严蔚敏老师的课件,看完后我豁然开朗,真不知道为什么她自己那本《数据结构(C语言版)》这里写的那么难懂,我是死活没看明白。

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有