数据结构第14讲-线索树与树和森林

《数据结构第14讲-线索树与树和森林》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.6赫夫曼树及其应用6.3.2线索二叉树1.何谓线索二叉树？遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。2.线索链表中结点的结构在二叉链表的结点结构中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示结点的左孩子

2、1lchild域指示结点的前驱RTag=0rchild域指示结点的右孩子1rchild域指示结点的后继二叉树二叉线索存储表示typedefenum{Link,Thread}PointerThr;//Link==0:指针，Thread==1:线索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;//左右孩子指针PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;3.线索二叉树图例线索二叉树及其存储结构（a）中序线索二叉树（b）中序线索链表123456701002

3、0131141050161171thrt01如何在线索树中找结点的后继？结合中序线索树若其右标志为“1”，右链是线索，右链直接指示了结点的后继；若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。1234567如何在线索树中找结点的前驱？结合中序线索树若其左标志为“1”，左链为线索，直接指示其前驱；若其左标志为“0”，左子树中最右下的结点为其前驱。1234567线索链表的中序遍历算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向头结点，头结点的左链lchild指向根结点，中序遍历//二叉线索树T的非递归

4、算法，对每个数据元素调用函数Visit。p=T->lchild;//p指向根结点while(p!=T){//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;//访问其左子树为空的结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}//访问后继结点p=p->rchild;}returnOK;}//IOTraver_T010020131141050161171T0114.如何建立线索化链表？由于线索化的实质是

5、将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。对二叉链表p进行中序线索化的递归算法(带头结点)StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)步骤：1.生成头结点Thrt，如果树非空，头结点指向树根，否则，回指自身；2.pre=Thrt;调用不带头结点的中序线索化的递归算法;3.最后一个结点线索化（指向头结点）voidInThreading(BiThrTreep){if(p){InThreading(p->lchild);//左子树线索化if(!p

6、->lchild){p->lchild=pre;p->ltag=Thread;}//前驱线索if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}//后继线索pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化}}InThreading对二叉链表p进行中序线索化的递归算法(不带头结点)0100203405067pre01pStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。Thrt=(BiT

7、hrTree)malloc(sizeof(BiThrNode));if(!Thrt)exit(OVERFLOW);Thrt->ltag=Link;Thrt->rtag=Thread;//建立头结点Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//空树，左指针回指自身else{//二叉树不为空树，进行线索化Thrt->lchild=T;//头结点的lchild指向二叉链表根pre=Thrt;//p