关于二叉树前序输入且输出结构的算法实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ElementType int
#define  MaxSize 511 //the number of the node is 2^levels-1
                     //and the max level is 9

//An array to store each value of the node in the tree by its index
int values[MaxSize];

//node structure constructor
typedef struct bt {
   ElementType data;
   struct bt *lchild, *rchild;
} BinaryTreeNode,*BTRoot;

//function declear
ElementType InOrder(BTRoot root);
ElementType PreOrder(BTRoot root);
ElementType PostOrder(BTRoot root);
void listTree(int l);
void addSpace(int i);

//the main function to excute
main()
{
  int i,l,n;

  BTRoot r=malloc(sizeof(BinaryTreeNode));
  printf("===================================================================\n");
  printf("BinaryTree list & 3-order program by SongNan @ 2004\n");
  printf("===================================================================\n");
  printf("The following instructions can help you to use it:");
  printf("\n");
  printf("1.To tell how many level(s) you want to use:(1-9)");
  printf("2.You should give the value to the current root(even a root of sub)\n");
  printf("3.If you want to create the left child for the current node press Y\notherwise,N\n");
  printf("4.Use the same way to create the right child for the current node\n");
  printf("See the result if all the creation has been done\n");
  printf("===================================================================\n");
  printf("\n");
  printf("How many levels of the tree you want to create?");
  scanf("%d",&l);
  n=pow(2,l)-1;
  for(i=0;i<=n;i++)
  {
    values[i]=-1;
  }
  CreateTree(r,1);
  printf("===================================================================\n");
  printf("\nPreorder :");
  PreOrder(r);
  printf("\nInorder :");
  InOrder(r);
  printf("\nPostorder:");
  PostOrder(r);
  printf("\n");
  printf("===================================================================\n");
  printf("The constructor of the tree comes here:\n");
  listTree(l);
  printf("===================================================================\n");
  printf("(ps:the value -1 means no such a node exist)\n");
  printf("===================================================================\n");
  printf("Copyright by SongNan @ 2004.11\n");
  printf("All codes & program");
  //for(i=0;i<31;i++)
   //printf("%d\n",values[i]);
  while(1) ;
  return 0;
}

//inorder function
InOrder(BTRoot root)
{
  if(!root) return 0;
  InOrder(root->lchild);
  printf("%4d",root->data);
  InOrder(root->rchild);
}

//preorder function
PreOrder(BTRoot root)
{
  if(!root) return 0;
  printf("%4d",root->data);
  PreOrder(root->lchild);
  PreOrder(root->rchild);
}

//postorder function
PostOrder(BTRoot root)
{
  if(!root) return 0;
  PostOrder(root->lchild);
  PostOrder(root->rchild);
  printf("%4d",root->data);
}
 /*receive the input data and create a node each time!*/
CreateTree(BTRoot root,int NodeNum) /* Preorder */
{
  ElementType x;
  int layer;
  char c;

  c='a';
  layer=log(NodeNum)/log(2)+1;
  printf("\nInput the root's value of the subtree %d:",NodeNum);
  scanf("%d",&x);
  root->data=x;
  values[NodeNum]=x;

   printf("Wanna create Leftchild for Node %d?(Y/N)",NodeNum);
   scanf("%1s",&c);
   if(c=='n'||c=='N') root->lchild=NULL;
    else
     {
       root->lchild=(BTRoot)malloc(sizeof(BinaryTreeNode));
       CreateTree(root->lchild,2*NodeNum);
     }

   printf("Wanna create Rightchild for Node %d?(Y/N)",NodeNum);
   scanf("%1s",&c);
   if(c=='n'||c=='N') root->rchild=NULL;
    else
     {
       root->rchild=(BTRoot)malloc(sizeof(BinaryTreeNode));
       CreateTree(root->rchild,2*NodeNum+1);
     }

  return 0;
}
//TO display the entire tree on the screen
void listTree(int Lv)
{
 int lv,count,i=1;

 for(lv=0;lv<Lv;lv++)
 {
   for(count=0;count<pow(2,lv);count++)
    {
      addSpace(pow(2,5-lv));
      printf("%d",values[i]);
      ++i;
    }
    printf("\n");
 }
}
void addSpace(int sn)
{
 int i;

 for(i=0;i<sn;i++)
  printf(" ");
}

本文地址：http://com.8s8s.com/it/it25435.htm