erchashu.rar_visual c

#include"shulei.h" #include<iostream.h> /*node* threadtree::FIOpre(node *t)//返回先根线索二叉树t的先根序列的第一个结点 { if(t!=NULL) return t; }*/ node *threadtree::FIOin(node *t)//返回中根线索二叉树t的中根序列的第一个结点 { if(t==NULL) return NULL; node *q; q=t; while(q->lthread==0) q=q->left; return q; } /*node *threadtree::FIOlast(node *t)//返回后根线索二叉树t的后根序列的第一个结点 { node *q; q=t; if(t->lthread==1) { if(t->rthread==1) return t; else return FIOlast(t->right); } else return FIOlast(t->left); }*/ /*node* threadtree::LIOpre(node *t)//返回先根线索二叉树t的先根序列的最后一个结点 { node *q; q=t; if(t->rthread==1) { if(t->lthread==1) return t; else return LIOpre(t->left); } else return LIOpre(t->right); }*/ node* threadtree::LIOin(node *t)//返回中根线索二叉树t的中根序列的最后一个结点 { if(t==NULL) return NULL; node *q=t; while(q->rthread==0) q=q->right; return q; } /*node* threadtree::LIOlast(node *t)//返回后根线索二叉树t的后根序列的最后一个结点 { if(t!=NULL) return t; }*/ //node *threadtree::PIOpre(node *t,node *p)//在以t为根结点的先根线索二叉树中搜索结点p的先根前驱结点 node *threadtree::PIOin(node *t,node *p)//在以t为根结点的中根线索二叉树中搜索结点p的中根前驱结点 { if(t==NULL||p==NULL)return NULL; node *q; node *first;//中根序列的首结点 first=FIOin(t); if(p==first) { q=NULL; return q; } else { if(p->lthread==1) { q=p->left; return q; } else { q=LIOin(p->left); return q; } } } /*node *threadtree::PIOlast(node *t,node *p)//在以t为根结点的后根线索二叉树中搜索结点p的后根前驱结点 { node *q; node *first;//后根序列的首结点 first=FIOlast(t); if(p==first) { q=NULL; return q; } else { if(p->rthread==1) { if(p->lthread==1) { q=p->left; return q; } else { q=LIOlast(p->left); return q; } } else { q=LIOlast(p->right); return q; } } } */ //node* threadtree::NIOpre(node *t,node *p)//在以t为根结点的先根线索二叉树中搜索结点p的先根后继结点 node* threadtree::NIOin(node *t,node *p)//在以t为根结点的中根线索二叉树中搜索结点p的中根后继结点 { if(t==NULL||p==NULL)return NULL; node *q=NULL; node *last; last=LIOin(t); if(p==last) { q=NULL; return q; } else { if(p->rthread==1) { q=p->right; return q; } else { return q=FIOin(p->right); } } } //node* threadtree::NIOlast(node *t,node *p)//在以t为根结点的后根线索二叉树中搜索结点p的后根后继结点 void threadtree::inorder(node*t)//中根遍历以结点t为根结点的中序线索二叉树 { node *q=FIOin(t);//中根序列首节点 while(q!=NULL) { cout<<q->data<<endl; q=NIOin(t,q); } //for(q=FIOin(t);q!=NULL;q=NIOin(t,q)) // cout<<q->data<<endl; } /*void threadtree::preorder(node*t)//先根遍历以结点t为根结点的先序线索二叉树 { node *q; q=FIOpre(t);//中根序列首节点 while(q!=NULL) { cout<<q->data<<endl; q=NIOpre(t,q); } } void threadtree::lastorder(node*t)//后根遍历以结点t为根结点的后序线索二叉树 { node *q; q=FIOlast(t);//中根序列首节点 while(q!=NULL) { cout<<q->data<<endl; q=NIOlast(t,q); } }*/ void threadtree::insertright(node *p,node *s)//插入一个结点p，作为结点s的右子节点 { if(s==NULL||p==NULL) return; p->right=s->right; p->rthread=s->rthread; p->lthread=1; p->left=s; //s->rthread=0; // s->right=p; if((s->rthread)==1) { s->right=p; s->rthread=0; } else { node *q=p->right; q=FIOin(q); q->lthread=1; q->left=p; s->rthread=0; s->right=p; } } //void threadtree::insertleft(node *p,node *s)//插入一个结点p，作为结点s的左子节点 //void threadtree::deleteleft(node *p,node *s)//删除结点s的左子结点p void threadtree:: deleteright(node *t,node *s)//删除结点s的右子节点 { node *p=s->right; if((p->lthread==1)&&(p->rthread==1)) { s->right=p->right; s->rthread=1; } if((p->lthread==1)&&(p->rthread==0)) { node *temp=FIOin(p->right); s->right=p->right; temp->left=s; } if((p->lthread==0)&&(p->rthread==1)) { node *temp=LIOin(p->left); s->right=p->left; temp->right=p->right; } if((p->lthread==0)&&(p->rthread==0)) { node *temp=LIOin(p->left); node *temp1=FIOin(p->right); s->right=p->left; temp1->left=temp; temp->right=p->right; temp->rthread=0; } } node *threadtree::create()//建立以root为根结点的尚未线索的二叉树 { node *q=NULL; node *root=NULL,*t1=NULL,*t2=NULL; int item; cin>>item; if(item==stop) { root=NULL; return root; } else { root=new node(item,NULL,NULL); if(root!=NULL) { t1=create(); root->left=t1; t2=create(); root->right=t2; return root; } } } /*int threadtree::count(node *t) { if(t!=NULL) return (count(t->left)+count(t->right)+1); else return 0; } void threadtree::threadingtree()//线索化以root为根结点的二叉树为中序线索二叉树 { node *root; int *a[count(root)]; a[0]=NULL; inorder(root,a[count(root)]); int front=0,rear=0,a[front]=a[rear]=getroot(); while(front<=rear) { if(a[front]!=NULL) { if(a[front]->getleft()!=NULL)a[++rear]=a[front]->getleft(); if(a[front]->getright()!=NULL)a[++rear]=a[front]->getright(); } front++; } a[1]=getfirstnode(root); a[1]->left=NULL; a[1]->lthread=1; if(a[1]->right!=NULL) a[1]->rthread=0; else { a[1]->rthread=1; a[1]->right=a[2]; } for(int i=2;i<=(count(root));i++) { if(a[i]->left==NULL) { a[i]->left=a[i-1]; a[i]->lthread=1; } else { a[i]->lthread=0; a[i]->left=a[i]->left; } if(a[i]->right==NULL) { a[i]->right=a[i+1]; a[i]->rthread=1; } else { a[i]->rthread=0; a[i]->right=a[i]->right; } } } } //void threadtree::inthreadingtree(node *t); void threadtree::inorder(node *t,node *) { int i=0; node * a[100]; if(t!=NULL) { inorder(t->left); cout<<t->data<<endl; a[i]=t; i++; inorder(t->right); } } treenode * getfirstnode(node *t) { node *p=t; if(p==NULL) return NULL; else { while(p->left!=NULL)p=p->left; return p; } }*/ void threadtree::creatthreadtree(int tostop)//建立以root为根结点的中序线索二叉树 { setstop(tostop); root=create(); } /*void threadtree::threadingtree(node *cur,node *pre)//中序线索化以cur为根的二叉树，pre表示cur的前驱 { if(cur!=NULL) {//按中序遍历方式进行线索化 if(cur->lthread==0) threadingtree(cur->left,pre);//线索化左子树 if(cur->left==NULL) {//cur无左孩子，加线索 cur->left=pre;//cur前驱为pre cur->lthread=1;//线索标志 } if(pre!=NULL&&pre->right==NULL) { pre->right=cur;//pre后继为cur pre->rthread=1;//线索标志 } pre=cur;//遍历下一结点时，cur为下一结点的前驱 if(cur->rthread==0) threadingtree(cur->right,pre);//线索化右子树 } } void threadtree::inthreadingtree() { node *pre=NULL;//开始线索化时前驱为空 threadingtree(root,pre);//中序线索化以root为根的二叉树 if(pre->right==NULL)//pre 为中序列中最后一个结点 pre->rthread=1;//如无右孩子，则加线索标志 }*/ void threadtree::treedisplay(node *t,int level) { if(t!=NULL) { treedisplay(t->right,level+1); cout<<endl; for(int i=0;i<level-1;i++) cout<<" "; cout<<t->data; treedisplay(t->left,level+1); } }