线索二叉树
线索二叉树
一、存储结构
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; //访问右子树
}
}作者：inss!w!
出处：https://www.cnblogs.com/Hfolsvh/