数据结构复习--遍历线索二叉树

遍历中序线索二叉树

FUNC in_next(p,thrt:thlinktp):thlinktp;
{在以thrt为头指针的中序线索二叉树上，查找指针p所指结点的后继}
    s:=*p.rchild;{当rtag=1，s指向后继，如果rtag=0则指向右孩子}
    IF *s.rtag=0 THEN{如果rtag=0,有右孩子，则进入循环，否则表明找到p的后继s}
        WHILE *s.ltag=0 DO
            s:=*s.lchild;
    RETURN(s);
ENDF{in_next}

 

PROC thrt_inorder(thrt:thlinktp);
{遍历以thrt为头指针的中序线索二叉树}
    p:=*thrt.lchild;{据线索二叉树的性质，p指向了根节点}
    WHILE *p.ltag=0 DO{定位，到要中序遍历的第一个结点}
        p:=*p.lchild;
    WHILE p<>thrt DO{开始遍历，调用in_next函数来找后继}
    [visit (*p.data); p:=in_next(p, thrt);]
ENDP;{thrt_inorder}

 

 

遍历后序线索二叉树

FUNC post_next(p,thrt:thlinktp):thlinktp;
{在以thrt为头指针的后序线索二叉树上，查找指针p所指结点的后继}
    s=PARENT(p,thrt);{查找p在thrt中的双亲}
    IF s=thrt THEN RETURN (thrt);{如果p是根，则返回头结点}
    IF *s.rchild=p OR *s.rtag=1 THEN {如果p为右孩子或独生左孩子，后继为双亲}
        RETURN (s);
    {如果双亲有两个孩子，且p为s的左孩子}
    WHILE *s.rtag=0 DO{如果有右孩子则进入循环，否则返回}
    [
        s:=*s.rchild;
        WHILE *s.ltag=0 DO s:=*s.lchild;{如果有左孩子，则进入循环}
    ]
    RETURN (s);
ENDF;{post_next}

 

PROC thrt_postorder (thrt:thlinktp);
{遍历以thrt为开头的后续线索二叉树}
    IF thrt<>*thrt.lchild THEN{如果不是空二叉树}
    [
        p:=*thrt.lchild;{p指向根}
        search:=true;
        {找到要遍历的第一个结点}
        WHILE search DO
        [
            WHILE *p.ltag=0 DO p:=*p.lchild;
            IF *p.rtag=0 THEN p:=*p.rchild;
                ELSE search:=false;
        ]
        WHiLE p<>thrt DO
        [visit(*p.data);p:=post_next(p,thrt)]
    ]
ENDP;{thrt_postorder}

 

 

先序遍历线索二叉树

FUNC pre_next(p,thrt:thlinktp):thlinktp;
{在以thrt为头指针的先序线索二叉树上，查找指针p所指结点的后继}
    IF *p.ltag=0 THEN RETURN (*p.lchild);{如果有左孩子，则左孩子为后继}
        ELSE RETURN (*p.rchild);
ENDF;{pre_next}

 

PROC thrt_preorder (thrt:thlinktp);
{遍历以thrt为头指针的先序线索二叉树}
    p:=*thrt.lchild;
    WHILE p<>thrt DO
    [
        visit(*p.data);
        p=pre_next(p,thrt);
    ]
ENDP;{thrt_preorder}