正在阅读：C++数据结构学习:二叉树(2)C++数据结构学习:二叉树(2)

2004-02-14 09:34 出处：PConline 作者：happycock/CSDN 责任编辑：linjixiong

线索化二叉树　　这是数据结构课程里第一个碰到的难点，不知道你是不是这样看，反正我当初是费了不少脑细胞——当然，恼人的矩阵压缩和相关的加法乘法运算不在考虑之列。我费了不少脑细胞是因为思考：他们干什么呢？很欣喜的看到在这本黄皮书上，这章被打了*号，虽然我不确定作者是不是跟我一个想法——线索化二叉树在现在的PC上是毫无用处的！——不知我做了这个结论是不是会被人骂死，^_^。　　为了证明这个结论，我们来看看线索化二叉树提出的缘由：第一，我们想用比较少的时间，寻找二叉树某一个遍历线性序列的前驱或者后继。当然，这样的操作很频繁的时候，做这方面的改善才是有意义的。第二，二叉树的叶子节点还有两个指针域没有用，可以节省内存。说真的，提出线索化二叉树这样的构思真的很精巧，完全做到了“废物利用”——这个人真应该投身环保事业。但在计算机这个死板的东西身上，人们的精巧构思往往都是不能实现的——为了速度，计算机的各个部件都是整齐划一的，而构思的精巧往往都是建立在组成的复杂上的。　　我们来看看线索化二叉树究竟能不能达到上面的两个目标。　　求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继，但是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，但是都不很直接；后序线索化能依次找到前驱，但是后继需要求双亲。可以看出，线索化成中序是最佳的选择，基本上算是达到了要求。　　节省内存。添加了两个标志位，问题是这两个位怎么储存？即使是在支持位存储的CPU上，也是不能拿位存储器来存的，第一是因为结构体成员的地址是在一起的，第二是位存储器的数目是有限的。因此，最少需要1个字节来储存这两个标志位。而为了速度和移植，一般来说，内存是要对齐的，实际上根本就没节省内存！然而，当这个空间用来储存双亲指针时，带来的方便绝对不是线索化所能比拟的，前面已经给出了无栈的非递归遍历。并且，在线索化二叉树上插入删除操作附加的代价太大。　　综上，线索化最好是中序线索化（前序后序线索化后还得用栈，何必要线索化呢），附加的标志域空间至少1个字节，在32位的CPU会要求对齐到4字节，还不如存储一个双亲指针，同样能达到中序线索化的目的，并且能带来其他的好处。所以，线索化二叉树在现在的PC上是毫无用处的！