首页 > 其他 > 详细

线索二叉树

时间:2021-05-03 14:47:22      阅读:21      评论:0      收藏:0      [点我收藏+]

一、存储结构

typedef enum{Link,Thread}PointerThr;
typedef struct BiThrNode{
    TElemType data;
    struct BiThrNode *lchild,*rchild;	//左右指针
    PointerThr LTag,RTag;	//左右标志
}BiThrNode,*BiThrTree;

二、线索链表的遍历算法

线索二叉树有n+1个空指针域
1.中序遍历的第一个结点:左子树上处于最左下的的结点
2.在中序线索化链表中结点的后继:
若无右子树,为后继线索所指结点;
否则为对其右子树进行中序遍历的第一个结点

为了方便,在二叉树的线索链表上添加了一个头结点,其左指针域指向根节点,其右指针域指向中序遍历时最后一个结点

void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)){
    p = T->lchild;	//p指向根结点
    while(p!=T){
        while(p->LTag==Link)	//退出循环时,p指向左子树最左下第一个结点
            p = p->lchild;
        if(!Visit(p->data))
            return ERROR;
        while(p->RTag==Thread && p->rchild!=T){	//访问p的后继结点
            p = p->rchild;
            Visit(p->data);
        }
        p = p->rchild;	//访问右子树
    }
}

线索二叉树

原文:https://www.cnblogs.com/Hfolsvh/p/14727176.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!