64遍历二叉树和线索二叉树 1)遍历中序线索二叉树 (1)中序线索二叉树中,找结点的后继算法 算法思頹:对任意结点p,若rtag=1,则 rchild 指向该结点的后继;若rtag=0,则 rchild指向该 结点的右孩子,此时,应从右孩子开始,沿左指 针前进,直到找到没有左孩子的结点s (ltag=1),则s航是p的后继,即后继是中序遍 历右子树时,访问的第一个结点;
6.4 遍历二叉树和线索二叉树 1）遍历中序线索二叉树 （1）中序线索二叉树中，找结点的后继算法 算法思想: 对任意结点p，若rtag=1，则rchild 指向该结点的后继；若rtag=0，则rchild指向该 结点的右孩子，此时，应从右孩子开始，沿左指 针前进，直到找到没有左孩子的结点s （ltag=1）,则s就是p的后继，即后继是中序遍 历右子树时，访问的第一个结点；
64遍历二叉树和线索二叉树 中序线索二叉树中,找结点的后继复法 BiThrTree in next(p, thrt) BiThrTree p, thrt /*在以thrt为头指针的中序线索二叉树上,* /*查找指针p所指结点的后继米/ s=p->rchild if (p->rtag==0) while (s->ltag=0 s=s→> Child 0 return s 1/in next
6.4 遍历二叉树和线索二叉树 中序线索二叉树中，找结点的后继算法 BiThrTree in_next(p, thrt) BiThrTree p, thrt; { /*在以thrt为头指针的中序线索二叉树上,*/ /*查找指针p所指结点的后继 */ s=p->rchild； if (p->rtag==0) while (s->ltag=0) s= s->lchild； return s; }//in_next p 1 s p 0 1 0 s