#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define NODE malloc(sizeof(Node))

typedef struct NodeType Node;
struct NodeType {
	float value;
	char  valid;
	Node *next, *left, *right;
};

void Linking(Node *T, int n)  /* Indice are initialized from 1 so that the leftson's index will be 2n */
{
Node *L, *R;
int  i; 
	if(T!=NULL) {
		L=T;
		for(i=0;i<n;i++) if((L=L->next)==NULL) return;
		if(L->valid) {
			T->left=L;
			Linking(L, 2*n);}
		else T->left=NULL;
		R=L->next;
		if(R->valid) {
			T->right=R;
			Linking(R, 2*n+1);}
		else T->right=NULL;
	}
}


Node *GetTree()
{
char list[2000], *item;
Node *Head, *Tail, *p;

	printf("Please input a complete binary tree as a number list using X as null node:\n");
	printf("Example: 3.14 52 X 7.83 45 (This tree has no right subtree).\n");

	gets(list);

	Head=NULL;
	item=NULL;

	item = strtok(list, " ,");
	while(item!=NULL){
		if(item!=NULL) {
			if(Head==NULL){
				Head=Tail=NODE;
			}
			else {
				Tail->next=NODE;
				Tail=Tail->next;
			}
			Tail->next = Tail->left = Tail->right = NULL;

			if(item[0]=='X') Tail->valid = 0;
			else {
				Tail->valid = 1;
				Tail->value = (float) atof(item);
			}
		}
		item = strtok(NULL, " ,");
	};
	
	p=Head;
	while(p!=NULL){
		if(p->valid) printf("->%f", p->value); else printf("-> X");
		p=p->next;
	}
	Linking(Head, 1);
	return(Head);
}

preorder(Node *T)
{
	if(T!=NULL){
		printf("->%f", T->value);
		preorder(T->left);
		preorder(T->right);
	}
}

main()
{
	Node *T;

		T=GetTree();
		printf("Preorder:"); preorder(T); printf("\n");
}