数据结构教学课件作者C语言PPT 第7章2.ppt

《数据结构教学课件作者C语言PPT 第7章2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、dltagrtagdatarchild标志位如果为0，表示指针指向孩子结点，为1表示指针为线索0A00B00E11C11D11F00G01H11I1NULLNULLt中序线索化算法INTHREAD(bithptr*p){if(p!=NULL){INTHREAD(p->lchild);if(p->lchild==NULL)p->ltag＝1;if(p->rchild==NULL)p->rtag＝1;if(pre!=NULL){if(pre->rtag==1)pre->rchild＝p;if(pre->ltag==1)pr

3、e->lchild＝pre;}pre＝p;INTHREAD(p->rchild);}}1、若*p的右子树为空，则p->rchild为右线索，直接指向*p的中序后继结点。2、若*p的右子树非空，则*p的中序后继必是其右子树中第一个遍历到的结点，也就是从*p的右孩子开始，沿左指针链往下查找，直到找到一个没有左孩子的结点为止。中序线索二叉树中，查找指定结点*p的中序后继结点pR1R2Rk最左下结点中序线索二叉树中求中序后继结点的算法bithptr*INORDERNEXT(bithptr*p){bithptr*q;if(p->

4、rtag==1)return(p->rchild);else{q＝p->rchild;while(q->ltag==0)q＝q->lchild;return(q);}}1、若*p的左子树为空，则p->lchild为左线索，直接指向*p的中序前驱结点。2、若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。中序线索二叉树中，查找指定结点*p的中序前驱结点pR1R2Rk最右下结点线索二叉树的遍历算法TRAVERSEINTHREAD(bithptr*p){if(p!=NULL){w

5、hile(p->ltag==0)p＝p->lchild;do{printf(“t%d”,p->data);p＝INORDERNEXT(p);}while(p!=NULL);}}线索二叉树的结点插入算法INSERTRIGHT(bithptr*p,bithptr*q){bithptr*s;s＝INORDERNEXT(p);q->ltag＝1;q->lchild＝p;p->rtag＝p->rtag;q->rchild＝p->rchild;p->rtag＝0;p->rchild＝q;if((s!=NULL)&&(s->l

6、tag==1))s->lchild＝q;}二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：1、若它的左子树非空，则左子树上所有结点的值均小于根结点；2、若它的右左子树非空，则右子树上所有结点的值均大于根结点；3、左、右子树本身又各是一棵二叉树。二、二叉排序树caozhaodingchenwangmaxiaduni二叉排序树结点的结构描述typedefstructnode{keytypekey;datatypeother;structnode*lchild,*rchild;}b

7、stnode;二叉排序树的结点插入bstnode*INSERTBST(bstnode*t,bstnode*s){bstnode*f,*p;p=t;while(p!=NULL){f=p;if(s->key==p->key)returnt;if(s->keykey)p=p->lchild;elsep=p->rchild;}if(t==NULL)returns;if(s->keykey)f->lchild=s;elsef->rchild=s;returnt;}二叉排序数的生成bstnode*CREATBST(

8、){bstnode*t,*s;keytypekey,endflag=0;datatype=data;t=NULL;scanf(“%d”,&key);while(key!=endflag){s=malloc(sizeof(bstnoe));s->lchild=s->rchild=NULL;s->key=key;scanf(“%d”,