数据结构书中说线索二叉树一般不设置fwd和bkwd指针，会浪费存储，为什么这么说

码拜

9年 ago

不论是设置fwd和bkwd，还是说它所推荐的设置ltag和rtag，两种设置每个节点都会占据四个单位存储空间（例如在C语言中指针变量和int都是四个字节），何来fwd和bkwd更浪费存储空间这一说法

解决方案

一个 char 四个字节，
两个也是，
假如位数比较少，
例如1Bit,32个标志占四个字节
大约如此，另外16Bits程序，int只有2个字节

fwd和bkwd能否浪费空间只是相对于不加这两个字段而言，原因是使用书上说的方式，不加这两个字段也可以实现线索二叉树。
也就是说结构体正常来说包括，left、right、fwd、bkwd、data。假如不加fwd、bkwd也可以实现。