|
线索化二叉树
这是数据结构课程里第一个碰到的难点，不知道你是不是这样看，反正我当初是费了不少脑细胞——当然，恼人的矩阵压缩和相关的加法乘法运算不在考虑之列。我费了不少脑细胞是因为思考：他们干什么呢？很欣喜的看到在这本黄皮书上，这章被打了*号，虽然我不确定作者是不是跟我一个想法——线索化二叉树在现在的PC上是毫无用处的！——不知我做了这个结论是不是会被人骂死，^_^。
为了证明这个结论，我们来看看线索化二叉树提出的缘由：第一，我们想用比较少的时间，寻找二叉树某一个遍历线性序列的前驱或者后继。当然，这样的操作很频繁的时候，做这方面的改善才是有意义的。第二，二叉树的叶子节点还有两个指针域没有用，可以节省内存。说真的，提出线索化二叉树这样的构思真的很精巧，完全做到了“废物利用”——这个人真应该投身环保事业。但在计算机这个死板的东西身上，人们的精巧构思往往都是不能实现的——为了速度，计算机的各个部件都是整齐划一的，而构思的精巧往往都是建立在组成的复杂上的。
我们来看看线索化二叉树究竟能不能达到上面的两个目标。
求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继，但是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，但是都不很直接；后序线索化能依次找到前驱，但是后继需要求双亲。可以看出，线索化成中序是最佳的选择，基本上算是达到了要求。
节省内存。添加了两个标志位，问题是这两个位怎么储存？即使是在支持位存储的CPU上，也是不能拿位存储器来存的，第一是因为结构体成员的地址是在一起的，第二是位存储器的数目是有限的。因此，最少需要1个字节来储存这两个标志位。而为了速度和移植，一般来说，内存是要对齐的，实际上根本就没节省内存！然而，当这个空间用来储存双亲指针时，带来的方便绝对不是线索化所能比拟的，前面已经给出了无栈的非递归遍历。并且，在线索化二叉树上插入删除操作附加的代价太大。
综上，线索化最好是中序线索化（前序后序线索化后还得用栈，何必要线索化呢），附加的标志域空间至少1个字节，在32位的CPU会要求对齐到4字节，还不如存储一个双亲指针，同样能达到中序线索化的目的，并且能带来其他的好处。所以，线索化二叉树在现在的PC上是毫无用处的！
由于对其他体系不太了解，以下观点姑妄听之。在内存空间非常充裕的现在，一个节点省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<2<data;
elsecout<<'';
}
else
{
cout<data;
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<3回顶部
打印树状结构的核心是按层次遍历二叉树，但是，二叉树有许多节点缺左或右子树，连带的越到下面空隙越大。为了按照树的结构打印，必须把二叉树补成完全二叉树，这样下面的节点就知道放在什么位置了——a.push(&zero);但是这样的节点不能让它打印出来，所以对应每个节点，有一个是否打印的标志，按理说pair结构很合适，为了简单我用了并列的两个队列，一个放节点指针——a，一个放打印标志——flag。这样一来，循环结束的标志就不能是队列空——永远都不可能空，碰到NULL就补一个节点——而是变成了到了满二叉树的最后一个节点2^(height+1)-1。——黄皮书对于树高的定义是，空树为的高度为－1。
对于输出格式，注意的是到了第1、2、4、8号节点要换行，并且在同一行中，第一个节点的域宽是后序节点的一半。上面的函数在树的层次少于等于5（height<=4）的时候能正常显示，再多的话就必须输出到文件中去ofstreamoutfile("out.txt");——如果层次再多的话，打印出来也没什么意义了。
二叉搜索树的实现
实际上就是在二叉树的基础上增加了插入、删除、查找。
#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)
{
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能最大限度的被这两个操作利用。
对于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语言版）》这里写的那么难懂，我是死活没看明白。
|
