vlambda博客
学习文章列表

数据结构 | 线索二叉树2 | 中序线索二叉树的构造(计算机408统考)

 点击上方"蓝字"
关注我们吧!


数据结构的学习可以分为八个模块:1.绪论,2.线性表,3.栈和队列,4.串,5.树与二叉树,6.图,7.查找,8.排序。


树与二叉树部分可分为:

其中线索二叉树部分有以下几个要点:

数据结构 | 线索二叉树2 | 中序线索二叉树的构造(计算机408统考)


数据结构 | 线索二叉树2 | 中序线索二叉树的构造(计算机408统考)
2
中序线索二叉树的构造


二叉树的线索化是将二叉链表中的空指针改为指向前驱后继线索。而前驱或后继的信息只有在遍历时才能得到,因此线索化实质就是遍历一次二叉树


以中序线索二叉树的建立为例。附设指针 pre 指向刚刚访问过的结点,指针 p 指向正在访问的结点,即 pre 指向 p前驱。在中序遍历的过程中,检查 p 左指针是否为,若为就将它指向 pre;检查 pre 的右指针是否为,若为空就将它指向 p

数据结构 | 线索二叉树2 | 中序线索二叉树的构造(计算机408统考)


通过中序遍历对二叉树线索化的递归算法如下∶

void InThread (ThreadTree &p,ThreadTree &pre) { if(p!=NULL){ InThread(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);    //递归,线索化右子树 } //if(p!=NULL)}


通过中序遍历建立中序线索二叉树的主过程算法如下∶ 

void CreateInThread (ThreadTree T) { ThreadTree pre=NUL;     if(T!=NULL){    //非空二叉树,线索化         InThread(T,pre);   //线索化二叉树        pre->rchild=NULL;     //处理遍历的最后一个结点         pre->rtag=1; }}

为了方便,可以在二叉树的线索链表上也添加一个头结点,令其 lchild 域的指针指向二叉树的根结点,其rchild 域的指针指向中序遍历时访问的最后一个结点; 令二叉树中序序列中的第一个结点lchild 域指针和最后一个结点 rchild 域指针均指向头结点。这好比为二叉树建立了—个双向线索链表。方便从前往后或从后往前对线索二叉树进行遍历。






本文章已加入菜单栏导航,可在“课程学习-数据结构2”处查看。


扫码关注我们吧
识别二维码,即可关注