27线索二叉树的遍历

线索二叉树的遍历：中序化二叉树主要是为访问运算服务的，这里遍历不需要借助栈，因为它的结点中隐含了线索二叉树的前驱和后继信息。利用线索二叉树，可以实现二叉树遍历的非递归算法。描述代码如下： 1、 求中序线索二叉树中序序列下的第一个结点 ThreadNode *Firstnode(ThreadNode *p){ While(p->ltag0) p=p->lchild; //最左下结点 Return p; } 2、 求中序线索二叉树中结点p在中序序列下的后继结点 ThreadNode *Nextnode(ThreadNode *p){ If(p->rtag0) return Firstnode(p->rchild); Else return p->rchild; //rtag==1直接返回后继线索 } 3、 利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历算法： Void Inorder(ThreadNode *T){ For(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode§) visit§; }