vlambda博客
学习文章列表

数据结构考研学习笔记(十三)——线索二叉树

文字:独木

排版:独木

图片:独木




数据结构考研学习笔记(十三)——线索二叉树

— 往期回顾 —

数据结构考研学习笔记(十三)——线索二叉树



数据结构考研学习笔记(十三)——线索二叉树

数据结构考研学习笔记(十三)——线索二叉树



数据结构考研学习笔记(十三)——线索二叉树



数据结构考研学习笔记(十三)——线索二叉树


线索二叉树的概念

线索化
若无左子树,则将左指针指向其前驱结点;
若无右子树,则将右指针指向其后继结点。
数据结构考研学习笔记(十三)——线索二叉树
数据结构考研学习笔记(十三)——线索二叉树

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








发现更多精彩