树和二叉树ppt课件.ppt

《树和二叉树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、应用第五章树和二叉树10/7/20211二叉树在一般情况下无法直接找到某结点在某种遍历序列中的前驱和后继结点。若增加指针域来存放前驱和后继结点信息，将大大降低存储空间的利用率（密度）。考察n个结点的二叉树，其中有n+1个空指针域，它们可以被用来存放“线索”加了线索的二叉树称为线索二叉树。一、线索二叉树10/7/20212线索二叉树结点的描述typedefintdatatype;typedefstructnode{intltag,rtag;datatypedata;structnode*lchild,*rchild;}bithptr;bithptr*pre;

2、lchildltagrtagdatarchild标志位如果为0，表示指针指向孩子结点，为1表示指针为线索10/7/202130A00B00E11C11D11F00G01H11I1NULLNULLt10/7/20214中序线索化算法INTHREAD(bithptr*p,bithptr*pre)//p为当前结点，pre为p的前驱结点，开始调用时p为根结点指针，pre为NULL{if(p!=NULL){INTHREAD(p->lchild,pre);//左子树线索化//若当前结点的左子树为空，则建立指向其前驱结点的前驱线索if(p->lchild==NULL){

3、p->ltag＝1;p->lchild＝pre;}elsep->ltag＝0;//若前驱结点不为空，且其右孩子为空，则建立该前驱结点指向当前结点的后续线索if(pre!=NULL&&pre->rchild==NULL){pre->rtag＝1;pre->rchild＝p;}elsep->rtag＝0;pre＝p;//中序向前遍历一个结点INTHREAD(p->rchild,pre);}}10/7/202151、若*p的右子树为空，则p->rchild为右线索，直接指向*p的中序后继结点。2、若*p的右子树非空，则*p的中序后继必是其右子树中第一个遍历到的结

4、点，也就是从*p的右孩子开始，沿左指针链往下查找，直到找到一个没有左孩子的结点为止。中序线索二叉树中，查找指定结点*p的中序后继结点10/7/20216pR1R2Rk最左下结点10/7/20217中序线索二叉树中求中序后继结点的算法bithptr*INORDERNEXT(bithptr*p){bithptr*q;if(p->rtag==1)return(p->rchild);else{q＝p->rchild;while(q->ltag==0)q＝q->lchild;return(q);}}10/7/202181、若*p的左子树为空，则p->lchild为左

5、线索，直接指向*p的中序前驱结点。2、若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。中序线索二叉树中，查找指定结点*p的中序前驱结点10/7/20219pR1R2Rk最右下结点10/7/202110线索二叉树的遍历算法TRAVERSEINTHREAD(bithptr*p){if(p!=NULL){while(p->ltag==0)p＝p->lchild;do{printf(“t%d”,p->data);p＝INORDERNEXT(p);}while(p!=NULL);}}10/7/202111线索二叉

6、树的结点插入算法INSERTRIGHT(bithptr*p,bithptr*q){bithptr*s;s＝INORDERNEXT(p);q->ltag＝1;q->lchild＝p;q->rtag＝p->rtag;q->rchild＝p->rchild;p->rtag＝0;p->rchild＝q;if((s!=NULL)&&(s->ltag==1))s->lchild＝q;}10/7/202112二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：1、若它的左子树非空，则左子树上所有结点的值均小于根结点；2、若它的右左

7、子树非空，则右子树上所有结点的值均大于根结点；3、左、右子树本身又各是一棵二叉树。二、二叉排序树10/7/202113caozhaodingchenwangmaxiaduni10/7/202114二叉排序树结点的结构描述typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;10/7/202115二叉排序树的结点插入//向一个二叉排序树中插入一个结点svoidINSERT(bitree*b,bitree*s){if(b==NULL)b=s;elseif(s->data==b->dat

8、a)return;//不做任何插入操作elseif(s->data