bitree.txt

二叉树的建立和遍历算法

#define TRUE           1
#define FALSE          0
#define OK             1
#define ERROR         0
#define INFEASIBLE    -1
#define OVERFLOW    -2
#define NULL           0
typedef int Status;
#include"stdio.h"
typedef enum {Link, Thread} PTag;
typedef struct BiTreeNode{
  char data;
  struct BiTreeNode *left,*right;
  PTag  ltag, rtag;
}BiTreeNode,*BiTreePtr;
BiTreePtr pre;
/**************************************/
Status CreatBiTree(BiTreePtr *T,char *tree){
  /*通过保存二叉树广义表的字符串tree建立链式存储结构*/
  BiTreePtr p,BT[100];
  int top=0,k,i=0;
  p=(BiTreeNode *) malloc (sizeof(BiTreeNode));
  while(tree[i]){
    switch(tree[i]){
      case' ':
	      break;
      case'(':
	      BT[top]=p;top++;
	      k=1;
	      break;
      case')':
	      if(top==-1){
	         printf("Wrong tree!");
	         exit(1);
	      }
	      top--;
	     break;
      case',':
	     k=2;
	     break;
      default:
	     p=(BiTreeNode *) realloc (sizeof(BiTreeNode));
         p->data=tree[i];p->left=p->right=NULL;
	     if((*T)->data==NULL) (*T)=p;
	     else
	        if(k==1) BT[top-1]->left=p;
	        else     BT[top-1]->right=p;
    }
    i++;
  }
  return OK;
}
/**************************************/
Status creatBiTree(BiTreePtr *T){
  BiTreePtr p;
  static char tree[100];
static int x=0;
if(x==0) scanf("%s%*[^\n]%*c",tree);
switch(tree[x]){
     case' ': break;
     case'(':
         x++;
         creatBiTree(&((*T)->left));
         if (tree[x]==',') {x++;creatBiTree(&((*T)->right));}
         if (tree[x]==')') {x++;creatBiTree(T);}
         break;
     case')': break;
     case',': break;
     case NULL: break;
     default:
         p=(BiTreeNode *) malloc(sizeof(BiTreeNode));
p->data=tree[x];p->left=p->right=NULL;
p->ltag=p->rtag=Link;
         *T=p;
         x++;
         creatBiTree(T);
  }
  return OK;
}

/**************************************/
Status PreOrderTraverse(BiTreePtr T, void(*visit)(char)){
  if(T){
    (*visit)(T->data);
    if(PreOrderTraverse(T->left,visit))
      if(PreOrderTraverse(T->right,visit)) return OK;
    return ERROR;
}
else return OK;
}


/*************************************/

Status InOrderTraverse(BiTreePtr T,void(*visit)(char)){
 if(T){
    if(InOrderTraverse(T->left,visit)){
       visit(T->data);
       if(InOrderTraverse(T->right,visit)) return OK;}
    return ERROR;
 }
else return OK;
}

/**************************************/

Status PostOrderTraverse(BiTreePtr T,void(*visit)(char)){
  if(T){
    if(PostOrderTraverse(T->left,visit))
      if(PostOrderTraverse(T->right,visit)){
        visit(T->data); return OK;}
    return ERROR;
}
else return OK;
}
/**************************************/
int BiTreeDepth(BiTreePtr T){
  if(T==NULL)
    return 0;
  else{
    int depthL=BiTreeDepth(T->left);
    int depthR=BiTreeDepth(T->right);
    return (depthL> depthR) ? depthL+1 : depthR+1;
  }
}
/**************************************/
Status Parent(BiTreePtr T, char e, BiTreePtr *P){
  /*在根指针T指向的树中查找指定结点，其结点值为e，并用P返回双亲结点位置*/
  static int k=0;
  if(T==NULL) return 0;
  else{
    if(T->data==e){
      /*若找到指定结点，则返回真，使k=0，表示未退出过递归*/
      k=0; return 1;
    }
    else{
      if(Parent(T->left,e,P)){
        /*向左子树查找指定结点*/
        if(k==0) *P=T;
        k=1;
	    return 1;
      }
      if(Parent(T->right,e,P)) {
        if(k==0) *P=T;
        k=1;
	    return 1;
      }
      return 0;
    }
  }
}

/**************************************/
Status DelBiTreeNode(BiTreePtr *root,BiTreePtr *T){
  /*删除T指向的结点*/
  BiTreePtr P;
  P=(BiTreeNode *) malloc (sizeof(BiTreeNode));
  P->data=NULL;
  if(*T!=NULL){
    DelBiTreeNode(T,&((*T)->left));
    DelBiTreeNode(T,&((*T)->right));
    if (Parent(*root, (*T)->data, &P) && P->data!=NULL){
      if(P->left==*T) P->left=NULL;
      if(P->right==*T) P->right=NULL;
    }
    free(*T);
  }
  return OK;
}

/**************************************/
Status InOrderThreading(BiTreePtr *T){
  BiTreePtr p;
  p=*T;
  if(p){
    InOrderThreading(&((*T)->left));
    if(!p->left) {p->ltag=Thread;p->left=pre;}
    if(pre&&!pre->right) {pre->rtag=Thread;pre->right=p;}
    pre=p;
    InOrderThreading(&((*T)->right));
  }
  return OK;
}

Status InOrderTraverseThr(BiTreePtr T,void(*visit)(char)){
  BiTreePtr p;
  p=T;
  while(p){
    while(p->ltag==Link) p=p->left;
    visit(p->data);
    while(p->rtag==Thread&&p->right!=NULL){
      p=p->right;visit(p->data);
    }
    p=p->right;
  }
  return OK;
}
/**************************************/
main(){
 BiTreePtr BT1,BT2;
  int i,j,m,k=0,n=0,e[100];
  char tree[100],value;
  do{
     for(i=1;i<=4;i++) printf("\n");
     printf(" Please Choose:\n");
     printf(" 1.Please first create the Bitree.\n");
     printf(" 2.Preorder  Nonrecursive\n");
     printf(" 3.Inorder Nonrecursive\n");
     printf(" 4.post order Nonrecursive.\n");
     printf(" 5.The Depth of the Tree.\n");
     printf(" 6.Find the parent of a Node.\n");
     printf(" 7.Delete Node.\n");
     printf(" 8.Inorder Threading.\n");
     printf(" 0.Exit\n ");
     scanf("%d%*[^\n]%*c",&k);
     switch(k){
       case 1:
		BT1=(BiTreeNode *) malloc (sizeof(BiTreeNode));
		BT1->data=NULL;
		BT1->left=BT1->right=NULL;
		printf("Enter the tree:\n ");
		/*
        scanf("%s%*[^\n]%*c",tree);
		CreatBiTree(&BT1,tree);
        */
		creatBiTree(&BT1);
		printf("\n Have initqueue successfully!");
        getch();
        break;
       case 2:
		printf(" \nNow the PreOrderTraverse tree is(DLR):\n");
		PreOrderTraverse(BT1,print);
        getch();
        break;
       case 3:
		printf("\n Now the InOrderTraverse tree is(LDR):\n");
		InOrderTraverse(BT1,print);
        getch();
        break;
       case 4:
		printf("\n Now the PostOrderTraverse tree is(LRD):\n");
		PostOrderTraverse(BT1,print);
        getch();
        break;
       case 5:
		printf("\n The Depth of the Tree is: %d\n",BiTreeDepth(BT1));
		getch();
        break;
       case 6:
		printf("\n Please input the value of the node:");
		BT2=(BiTreeNode *) malloc (sizeof(BiTreeNode));
		BT2->data=NULL;
		scanf("%c%*[^\n]%*c",&value);
        if(Parent(BT1, value, &BT2)){
		   if(BT2->data==NULL) printf("\n The Node is root!!\n");
           else printf("\n The value of its parents is: %c\n",BT2->data);
		}
		else printf("\n Node Not Found!!!\n");
		getch();
		break;
       case 7:
		printf("\n Please input the value of the node:");
		BT2=(BiTreeNode *) malloc (sizeof(BiTreeNode));
		BT2->data=NULL;
        scanf("%c%*[^\n]%*c",&value);
        if(Parent(BT1, value, &BT2)){
		   if(BT2->data==NULL) DelBiTreeNode(&BT1,&BT1);
           else{
			 if(value==BT2->left->data) DelBiTreeNode(&BT1,&(BT2->left));
			 if(value==BT2->right->data) DelBiTreeNode(&BT1,&(BT2->right));
           }
		}
		else printf("\n Node Not Found!!!\n");
		break;
      case 8:
		printf("\n Now the InOrderTraverse Threading tree is(LDR):\n");
		InOrderThreading(&BT1);
        InOrderTraverseThr(BT1,print);
        getch();
        break;
     }
   }while(k!=0);
}