线索二叉树有效求解问题

首先，两个结论：

前不能前：前序线索二叉树没有有效算法能够通过指针找到前驱

后不能后：后序线索二叉树没有有效算法能够通过指针找到后继

然后讨论中序线索二叉树找后继

ThreadNode *Nextnode (ThreadNode *p) {
    if(p->rtag==0) return Firstnode(p->rchild); //右子树中最左下结点
    else return p->rchild;          // rtag==1 则直接返回后继线索
}

若A有右孩子，这个函数将会找到A的右孩子并一直往左走，停下的瞬间就是他的后继节点

若没有便会直接访问他的后继指针

寻找前驱也很简单，只需要寻找左孩子的最后一个右super孙子结点，无需赘述。也就是中序线索二叉树可以完美找到自己的前驱后继

我们再以B为当前节点讨论，若是先序线索二叉树，B（因为有左孩子）则无法找到他的大爹结点，也就是前驱A

若是后序线索二叉树，B（因为有右孩子）则无法找到他的亲爹指点，也就是后继A

因此前不能前后不能后，中都中！