数据结构考研学习笔记(十三)——线索二叉树
文字:独木
排版:独木
图片:独木
— 往期回顾 —
线索二叉树的概念
线索化
若无左子树,则将左指针指向其前驱结点;
若无右子树,则将右指针指向其后继结点。
typedef struct ThreadNode {
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag, rtag;
}ThreadNode,*ThreadTree;
这种结点结构构成的二叉链表作为二叉树的存储结构,称为线索链表
前驱结点
若左指针为线索,则其指向结点为前驱结点
若左指针为左孩子,则其左子树的最右侧结点为前驱结点
后驱结点
若右指针为线索,则其指向结点为后驱结点
若右指针为右孩子,则其右子树的最左侧结点为后驱结点
中序线索二叉树线索化
void InThread(ThreadTree &p,ThreadTree &pre) {
if(p! == NULL){
inrhread (p -> lchild,pre);
if(p->lchild == NULL){
p->lchild = pre;
p->ltag = 1;
}
if(pre!=NULL && pre->rchild==NULL){
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
InThread(p->rchild, pre);
}
}
void createInThread(ThreadTree T){
ThreadTree pre = NULL;
if(T!=NULL)[
InThread(T, pre);
pre->rchild = NULL;
pre->rtag = l;
中序线索二叉树遍历
找最左
ThreadNode *Firstnode (ThreadNode *p){
while(p->ltag o)
p= p->lchild;
return p;
找后继
ThreadNode *Nextnode (ThreadNode *p){
if(p->rtag == o)
return Firstnode (p->rchild) ;
else
return p->rchild;
循环的后继
void Inorder (ThreadNode *T){
for(ThreadNode *p=Firstnode(T); p!=NULL;p=Nextnode (p))//空遍历结束
visit(p);
)
End
1
发现更多精彩