Question

线索二叉树的线索二叉树结构

Answer 1

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。现将二叉树的结点结构重新定义如下： lchild ltag data rtag rchild 其中：ltag=0 时lchild指向左子女；
ltag=1 时lchild指向前驱；
rtag=0 时rchild指向右子女；
rtag=1 时rchild指向后继；