#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(" ");
}
