线索二叉树为啥使用标志域而不直接添加指向前驱和后继的指针域
泻药。一个指针，可能占用4字节，也可能8字节，很占内存的。设计数据结构，不仅要考虑大O表示，也就是广义的、大概的复杂度；还要考虑具体实现时，如何省空间。这就是科学和工程的结合。用tag的话，每个tag需要一个bit。两个bit的话，由于计算机最小的寻址范围是字节，因此，这里一般要用一个字节来表示。一个字节，总比两个指针八个字节甚至十六个字节，来的省吧。别忘了，这可是一个节点就省了7个字节甚至15个字节啊！有没有可能再省一省？可以的。指针一般是对齐的，最后两位一般是00，所以，也可以把tag信息放到这里。天呐？这么抠门？有必要这么省？是的。linux里对于红黑树里的color信息，就是这么做的。也就是传说中的 use the least significant bit of one of the pointers in the node to store the color information
■网友
普通二叉树中每个节点都有指向左右儿子的指针，但其中一半的指针是空的，线索二叉树是为了用这些空指针记录一定的前驱后继信息以方便先序遍历及相关操作。左（右）标示域用来区分每个指针是真的指向左（右）儿子还是前驱（后继），每个标示域只需1bit额外空间，每个节点2bit空间。题主意思是每个节点都加一个前驱后继指针，那样就是每个节点两个指针的额外空间了。
■网友
谢邀指针其实挺大的，64位程序的指针可是8字节！标志位几个bit就够了……我曾经设计过一个内存控制极为严苛条件下的自动机，转移字符才1字节，转移的指针居然要8字节，这也太不经济了，最后的解决方案就是自己写了个类似于内存池的东西，指针全部改成偏移量，整体的设计容量上升了十倍左右，速度也有很大提升（实际评测得出的，我觉得主要是因为对于cache的影响）对于写基础组件的人来说，这点内存是不能不考虑的，越底层的部件对于上层的影响越大（当然Unix这样把\\r\都省掉一个的单说……）。Linux在这种吝啬上也算是代表了，可以参考一下。利益相关： 数着字节过日子的cpp程序猿……
■网友
在达到目的的前提下提高存储密度
■网友
呵呵 你以为标志域跟前驱和后继的所占的存储空间一样么 ，一个是1，一个是n.这就像问路 对于问路的来说 当然希望地址越详细越好 但是随着地址的详细度增加 地址的信息量也就越大 对于被问的来说 最省事的回答 是 否 这两个回答 问路的人一路问下去 就行啦
推荐阅读
- 为啥看到书柜上的藏书会有心旷神怡的感觉
- 为啥知乎上普便有一种【我在北上广深打工，所以拥有更好的视野】这样的错觉
- 为啥工商银行的用户体验如此之差
- 汽车|看了中消协4S店服务测评调查结果，终于知道法系车为啥卖不好了
- 你为啥从窝窝商城离职?
- 为啥5G和2.4G默认的BSSID是相同的
- 为啥电器实体店的价格比淘宝贵那么多
- 现在在线学习视频有很多了，为啥大部分人还是喜欢下载下来观看
- 为啥到现在你还没有女朋友 ?
- 天赐的声音|33岁张雨绮为啥总离婚？看过这些照片就明白了，都是性感惹得祸