1 //邻接表存储结构定义  2 #define MAXVEX 100  3 struct ArcNode  4 {  5     int adjvex;  6     char info;  7     struct AecNode *nextarc;  8 };  9 struct vexnode 10 { 11     char data; 12     struct ArcNode*firstarc; 13 }; 14 typedef struct vexnode AdjList[MAXVEX]; 15 //通过用户交互产生一个有向图的邻接表 16 void createbgraph(AdjList*&g,int &n) 17 { 18     int e,i,s,d; 19     struct ArcNode*p; 20     printf("结点数(n)和边数(e):"); 21     printf("%d%d",&n,&e); 22     for(i=0;i
     
      data); 26         g[i]->firstarc=NULL; 27     } 28     for(i=0;i
      
       adjvex=d; 34         p->info=g[d]->data; 35         p->nextarc=g[s]->firstarc;//*p插入到顶点s的邻接表中 36         g[s]->firstarc=p; 37     } 38 } 39  40 //输出有向图的邻接表 41 void dispbgraph(AdjList*g,int n) 42 { 43     int i; 44     struct ArcNode *p; 45     printf("图的邻接表表示如下:\n"); 46     for(i=0;i
       
        data); 49         p=g[i]->firstarc; 50         while(p!=NULL) 51         { 52             printf("(%d,%c)->",p->dajvex,p->info); 53             p=p->nextarc; 54         } 55         printf("\n"); 56     } 57 } 58  59 //深度优先搜索的递归函数 60 int visited[MAXVEX]; 61 void dfs(AdjList*adj,int v0) 62 { 63     struct ArcNode*p; 64     visited[v1]=1; 65     prinf("%d",v0); 66     p=adj[v0]->firstarc; 67     while(p!=NULL) 68     { 69         if(visited[p->adjvex]==0) 70             dfs(adj,p->adjvex); 71         p=p->nextarc; 72     } 73 } 74 int visited[MAXVEX]; 75 void bfs(AdjList *adj,int vi)//广度优先遍历 76 { 77     int front=0,rear=0,v; 78     struct ArcNode *p; 79     visited[vi]=1;//访问初始顶点vi 80     printf("%d",vi); 81     rear++; 82     queue[rear]=vi; 83     while(front!=rear)//队列不空时循环 84     { 85         front=(front+1)%MAXVEX; 86         v=queue[front];//按访问次序依次出队列 87         p=adj[v]->firstarc;//找v的下一个邻接点 88         while(p!=NULL) 89         { 90             if(visited[p->adjvex]==0) 91             { 92                 visited[p->adjvex]=1; 93                 printf("%d",p->adjvex);//访问该点并使之入队列 94                 rear=(rear+1)%MAXVEX; 95                 queue[rear]=p->adjvex; 96             } 97             p=p->nextarc;//找v的下一个邻接点 98         } 99     }100 }101 102 //将一个无向图的邻接矩阵转换成邻接表103 void mattolist(AdjMatrix a,AdjList *&g)104 {105     int i,j,n;106     n=a.n;107     ArcNode *p;108     for(i=0;i
        
         =0;j++)112         if(a.edges[i][j]!=0)113     {114         p=(ArcNode*)malloc(sizeof(ArcNode));115         p->adjvex=j;116         p->nextarc=g[i]->firstarc;//添加的是新分配的p节点117         g[i]->firstarc=p;118     }119 }120 121 //求无向图的G的连通分量个数122 int getnum(AdjList*g)123 {124     int i,n=0,visited[MAXVEX];125     for(i=0;i
         
          n;i++)129         if(visited[i]==0)130     {131         n++;132         dfs(g,i);133     }134     return n;135 }136 //判断vi到vj是否可达137 int visited[MAXVEX];138 void connected(AdjList adj,int i,int j,int &c)139 {140     int k;141     if(i==j)142         c=1;143     else144     {145         k=0;146         c=0;147         while(k
          
           -1)202 {203 p=St[top];204 top--;205 printf("%d",p->data);206 if(p->rchild!=NULL)207 {208 top++;209 St[top]=p->rchild;210 }211 if(lchild!=NULL)212 {213 top++;214 St[top]=p->lchild;215 } 216 }217 }218 }219 //后序遍历二叉树的非递归算法220 void psorder(BTree*t)221 {222 BTree *St[MaxSize];223 BTree *p;224 int flag,top=-1;//栈指针置初值225 do226 {227 while(t)//将t的所有左结点入栈228 {229 top++;230 St[top]=t;231 t=t->lchild;232 }233 p=NULL;//p指向当前结点的前一个已访问的结点234 flag=1;//设置t的访问标记为已访问过235 while(top!=1&&flag)236 {237 t=St[top];//取出当前的栈顶元素238 if(t->rchild==p)//右子树不存在或已被访问过，访问之239 {240 printf("%c",t->data);241 top--;242 p=t;243 }244 else{t=t->rchild;245 flag=0;}246 }247 }while(top!=-1);248 }249 250 //求二叉树指定结点的层次251 int level(b,x,h)252 {253 int h1;254 if(b==NULL)255 {256 return 0;257 }258 else if(b->data==x)259 {260 return h;261 }262 else263 {264 h1=level(b->lchild,x,h+1)；265 if(h!=0)266 return h1;267 else268 return level(b->rchild,x,h+1);269 }270 }271 272 //按层次遍历二叉树273 void translevel(BTree*b)274 {275 struct node276 {277 BTree*vec[MaxSize];278 int f,r;//对头和对尾279 }Qu;280 Qu.f=0;//置队列尾空队列281 Qu.r=0;282 if(b!=NULL)283 printf("%c ",b->data);284 Qu.vec[Qu.r]=b;//结点指针进入队列285 Qu.r=Qu.r+1；286 while(Qu.f
           
            lchild!=NULL)291 {292 printf("%c",b->lchild->data);293 Qu.vec[Qu.r]=b->lchild;294 Qu.r=Qu.r+1;295 }296 if(b->rchild!=NULL)297 {298 printf("%c ",b->rchild->data);299 Qu.vec[Qu.r]=b->rchild;300 Qu.r=Qu.r+1;301 }302 }303 printf("\n");304 }305 //判断两棵二叉树是否相似306 int like(BTree*b1,BTree *b2)307 {308 int like1,like2;309 if(b1==NULL&&b2==NULL)310 return 1;311 else if(b1==NULL||b2)312 return 0;313 else314 {315 like1=like(b1->lchild,b2->lchild);316 like2=like(b1->rchild,b2->rchild);317 return (like1&&like2);318 }319 }320 321 //释放二叉树所占用的全部存储空间322 void release(BTree*b)323 {324 if(b!=NULL)325 {326 release(b->lchild);327 release(b->rchild);328 free(b);329 }330 }331 //判断是否为完全二叉树332 #define MAX 100333 int fullbtree1(BTree*b)334 {335 BTree*Qu[Max],*p;//定义一个队列，用于分层判断336 int first=0,rear=0,bj=1,cm=1;337 if(b!=NULL)//cm表示表示整个二叉树是否为完全二叉树，bj表示到目前为止所有节点均有左右孩子338 {339 rear++;340 Qu[rear]=b;341 while(first!=rear)342 {343 first++;344 p=Qu[first];345 if(p->lchild==NULL)346 {347 bj=0;348 if(p->rchild!=NULL)349 cm=0;350 }351 else352 {353 cm=bj;354 rear++;355 Qu[rear]=p->lchild;356 if(p->rchild==NULL)357 bj=0;358 else359 {360 rear++;361 Qu[rear]=p->rchild;362 } 363 } 364 }365 return cm;366 }367 return 1;368 }369 370 //上述的算法2371 #define MaxNum 100372 typedef char Sbtree[MaxNum];373 int fullbtree2(Sbtree A,int n)374 {375 int i;376 for(i=1;i<=n;i++)377 if(A[i]=' ')378 return 0;379 return 1;380 }381 382 //根据数组，建立与之对应的链式存储结构383 void creab(char tree[],int n,int i,BTree &b)384 {385 if(i>n)386 b=NULL;387 else388 {389 b=(BTree*)malloc(sizeof(BTree));390 b->data=tree[i];391 creab(tree,n,2*i,b->lchild);392 creab(tree,n,2*b+1,b->rchild);393 }394 }395 396 //求根节点root到p所指节点之间的路径397 void path(BTree*root,BTree*p)398 {399 BTree*St[MaxSize],*s;400 int tag[MaxSize];401 int top=-1,i; 402 s=root;403 do404 {405 while(s!=NULL)//扫描左结点，入栈406 {407 top++;408 St[top]=s;409 tag[top]=0;410 s=s->lchild;411 }412 if(top>-1)413 {414 if(tag[top]==1)//左右节点均已访问过，则要访问该结点415 {416 if(St[top]==p)//该结点就是要找的点417 {418 printf("路径：");//输出从栈底到栈顶元素的构成路径419 for(i=1;i<=top;i++)420 printf("%c ",St[i]->data);421 printf("\n");422 break;423 }424 top--;425 }426 else427 {428 s=St[top];429 if(top>0)430 {431 s=s->rchild;//扫描右结点432 tag[top]=1;//表示当前结点的右子树已访问过433 }434 435 }436 }437 }while(s!=NULL||top!=1)438 }439 440 //计算p和q两结点的共同最近的祖先441 BTree *ancestor(BTree*root,BTree*p,BTree*q)442 {443 BTree*St[MaxSize],&anor[MaxSize],*b,*r;444 int tag[MaxSize],find=0;445 int top=-1;446 b=root;447 do448 {449 while(b!=NULL)//扫描左结点450 {451 top++;452 St[top]=b;453 tag[top]=0;454 b=b->lchild;455 }456 if(top>-1)457 {458 if(tag[top]==1)459 {460 if(St[top]==p)//找到p所指结点，则将其祖先复制到anor中461 for(i=1;i<=top;i++)462 anor[i]=St[i];463 if(St[top]==q)//找到q所指结点，则比较找出最近的共同祖先464 {465 j=top;466 while(!find)467 {468 k=i-1;469 while(k>0&&St[j]!=anor[k])470 k--;471 if(k>0)472 {473 find=1;474 r=anor[k];475 }476 else477 j--;478 }479 }480 top--;481 }482 else483 {484 b=St[top];485 if(top>0&&!find)486 {487 b=b->rchild;488 tag[top]=1;489 }490 }491 }492 }while(!find&&(b!=NULL||top!=0));493 return r;494 }495 //假设二叉树中之多有一个数据域值为x，如结点为x，则拆去以该节点为跟的二叉树496 BTree *dislink(BTree*&t,elemtype x)497 {498 BTree *p,*find;499 if(t!=NULL)//t为原二叉树，拆开后的第一课二叉树，分拆成功后返回第二颗二叉树500 {501 if(t->data==x)//根结点数据域为x502 {503 p=t;504 t=NULL;505 return p; 506 }507 else508 {509 find=dislink(t->lchild,x);510 if(!find)511 find=dislink(t->rchild,x);512 return (find);513 }514 }515 516 else return (NULL);517 }518 519 //双序遍历二叉树520 void dorder(BTree *b)521 {522 if(b!=NULL)523 {524 printf("%c ",b->data);525 dorder(b->lchild);526 printf("%c ",b->data);527 dorder(b->rchild);528 }529 }530 531 //计算一颗二叉树的所有节点数532 int nodes(BTree *b)533 {534 int num1,num2;535 if(b==NULL)536 return(0);537 else538 {539 num1=nodes(b->lchild);540 bum2=nodes(b->rchild);541 return(num1+num2+1);542 }543 }544 545 //求一颗给定二叉树的单孩子的结点数546 int onechild(BTree*b)547 {548 int num1,num2,n=0;549 if(b==NULL)550 return 0;551 else if((b->lchild==NULL&&b->rchild!=NULL)||(b->lchild!=NULL&&b->rchild==NULL))552 n=1;553 num1=onechild(b->lchild);554 num2=onechild(b->rchild);555 return (num1+num2+n);556 }557 //表示父子，夫妻，兄弟关系的病=并且恩能够查找任一双亲结点的所有儿子的函数558 void find(BTree*b,int p)559 {560 BTree *q;561 q=findnode(b,p);562 if(q!=NULL)563 {564 q=q->lchild;565 q=q->rchild;566 while(q!=NULL)567 {568 printf("%c",q->data);569 q=q->rchild;570 }571 }572 573 }574 BTree*findnode(BTree*b,int p)575 {576 BTree*q;577 if(b==NULL)578 return NULL;579 else if(b->data==p)580 return b;581 else582 {583 q=findnode(b->lchild,p);584 if(q!=NULL)585 return q;586 else587 return(findnode(b->rchild,p));588 }589 }590 //由前序序列和中序序列构造该二叉树591 BTree *restore(char *ppos,char *ipos,int n)592 {593 BTree*ptr;594 char *rpos;595 int k;596 if(n<=0)597 return NULL;598 ptr=(BTree*)malloc(sizeof(BTree));599 ptr->data=*ppos;600 for(rpos=ipos;rpos
            
             lchild=restore(ppos+1,i,pos,k);//分别从左右进行遍历，构造二叉树605 ptr->rchild=restore(ppos+1+k,rpos+1,n-1-k);606 return ptr;607 }608 609 //已知中序序列和后序序列，建立起该二叉链结构的非递归算法610 //in[1……n],post[1^n]是中序序列和后序序列的两数组611 //二叉树的二叉链结点类型定义为:612 typedef struct613 {614 int lchild,rchild;615 int flag;616 char data;617 }618 619 #include
             
              620 #include
              
               621 #define MaxSize 100622 BTree B[MaxSize];623 int ctree(char in[],char post[])624 {625 int i=0,j,t,n,root,k;626 while(in[i]!='\0')//把in[i]中元素赋完627 {628 B[i].data=in[i];629 B[i].lchild=B[i].rchild=-1;630 B[i].flag=i;631 i++;632 }633 n=i;//n存放结点个数634 k=0;635 while(post[n-1]!=B[k].data)636 k++;637 root=k;638 for(i=n-2;i>=0;i--)639 {640 t=k;641 j=0;642 while(post[i]!=B[j].data)643 j++;644 while(t!=-1)//将B[j]插入到以k为结点的二叉树中645 if(B[j].flag
               
                B[t].flag)655 {656 if(B[t].rchild==-1)657 {658 B[t].rchild=j;659 t=-1;//插入成功后让t=-1660 }661 else t=B[t].rchild;662 }663 }664 return root;//返回根节点下标665 }666 //二叉树从根节点到每个叶子结点的路径667 typedef struct node668 {669 elemtype data;670 struct node*lchild,*rchild;671 struct node *parent;672 }BTree;673 674 #deine N 10//设二叉树中最长路径上结点个数不超过N675 void disppath(BTree *p)//输出一条从当前叶子节点*p的一条路径676 {677 if(p->parent!=NULL)678 {679 disppath(p->parent);680 printf("%c ",p->data);681 }682 else683 printf("%c ",p->data);684 }685 void path(BTree*b)686 {687 BTree *St[N],*p;688 int top=-1;689 if(b!=NULL)690 {691 b->parent=NULL;//根节点的父节点指针置为空692 top++;//根节点入栈693 St[top]=b;694 while(top>=0)//栈不空时循环695 {696 p=St[top];//退栈并访问该结点697 top--;698 if(p->lchild==NULL&&p->rchild==NULL)//为叶子节点时699 {700 disppath(p);701 printf("\n");702 }703 if(p->rchild!=NULL)//右孩子入栈704 {705 p->rchild-->parent=p;706 top++;707 St[top]=p->rchild;708 }709 if(p->rchild!=NULL)//左孩子入栈710 {711 p->lchild->parent=p;712 top++;713 St[top]=p->lchild;714 }715 }716 }717 }718 719 //终须线索二叉树求后续结点的算法720 //并依此写出终须线索二叉树的非递归算法721 //在终须线索二叉树中找一个结点后续的过程：若该结点有右线索，则右孩子为后续结点，否则，其右子树最左下的孙子便是后续结点，722 TBTree*succ(TBTree*p)723 {724 TBTree*q;725 if(p->rtag==1)726 return p->rchild;727 else728 {729 q=p->rchild;730 while(q->ltag==0)731 q=q->lchild;732 return q;733 }734 }735 //求一个结点前驱736 TBTree *pre(TBTree*p)737 {738 TBTree*q;739 if(p->ltag==1)740 return p->lchild;741 else742 {743 q=p->lchild;744 while(q->rtag==0)745 q=q->rchild;746 return q;747 }748 }749 750 void inorder(TBTree*root)//751 {752 TBTree*p,*head;753 if(root!=NULL)754 {755 head=root;756 p=root;757 while(p!=NULL)//循环结束后，head指向中序遍历的头结点758 {759 head=p;760 p=pre(p);761 }762 p=head;//从头结点开始中序遍历763 do764 {765 printf("%c ",p->data);766 p=succ(p);767 }while(p!=NULL);768 }769 }