bitree.cpp

图的创建和遍历

// 二叉树操作演示
#include <stdio.h>
#include <conio.h>
#include <alloc.h>

typedef struct node{
  char c;
  struct node *l,*r;
}node,*link;

char ch;
link t=NULL;

void creatr(link &t){  // 用扩展先序序列建二叉树
  char ch;
  ch=getche();
  if(ch==' ') t=NULL;
  else{
    t=(link)malloc(sizeof(node)); t->c=ch;
    creatr(t->l); creatr(t->r);
  }
}

void destroyt(link &t){ // 销毁二叉树
  link p;
  if(t){
    destroyt(t->l); destroyt(t->r);
    free(t);
  }
}

void pretravel(link t){
  if(t){
    printf("%2c",t->c);
    pretravel(t->l); pretravel(t->r);
  }
}

void intravel(link t){
  if(t){
    intravel(t->l); printf("%2c",t->c); intravel(t->r);
  }
}

void postravel(link t){
  if(t){
    postravel(t->l); postravel(t->r); printf("%2c",t->c);
  }
}

void leaves(link t){    // 打印叶子
  if(t){
    if(!(t->l)&&!(t->r)) printf("%2c",t->c);
    leaves(t->l); leaves(t->r);
  }
}

void prtree(link t,int k){  // 打印输出二叉树
  if(t){
    prtree(t->r,k+1);
    printf("%*c",4*k,t->c);
    if(t->l&&t->r) ch='<';
    else
      if(t->r) ch='/';
      else
	if(t->l) ch='\\';
	else ch=' ';
    printf("%c\n",ch);
    prtree(t->l,k+1);
  }
}

main(){
  clrscr();
  printf("             1.create tree  2.travel treee  3.leaves  4.destroy  0.Exit");
  window(1,2,80,25);
  while(ch!=48){
    gotoxy(36,3); printf("Chose:");
    ch=getch(); clrscr(); gotoxy(15,5);
    switch(ch){
      case '1': printf("Enter a extended preoder sequence:");
	if(t) destroyt(t); creatr(t); break;
      case '2': printf("Travel_Sequence:\n");
	printf("Pre_Oder: "); pretravel(t);
	printf("\nIn_Oder:  "); intravel(t);
	printf("\nPost_Oder:"); postravel(t);
	break;
      case '3': printf("Tree's leaves: "); leaves(t); break;
      case '4': destroyt(t); t=NULL; break;
      case '0': destroyt(t); window(1,1,80,25); return 0;
    }
    gotoxy(1,10); prtree(t,1);
  }  return 1;
}