#include <stdio.h>

#include <stdlib.h>



typedef struct _BinaryTree{

	int key;

	struct _BinaryTree *left;

	struct _BinaryTree *right;

}BinaryTree;



/* seq[] from 1 to n; sw[0] = 0 */

void secondOptimal(BinaryTree **T, int seq[], float sw[], int low, int high)

{

	BinaryTree *p=NULL;

	int i = low;

	float min = abs(sw[high] - sw[low-1]);

	float dp = 0;

	int j;

	for(j = low+1; j < high; j++){

		dp = abs( (sw[high] - sw[j]) - (sw[j-1] - sw[low-1]) );

		if(min > dp ){

			min = dp;

			i = j;	

		}		

	}

	p = (BinaryTree *)malloc( sizeof(BinaryTree) );

	*T = p;

	p->key = seq[i];

	if( i == low ){

		p->left = NULL;	

	}else{

		secondOptimal(&(p->left), seq, sw, low, i-1);	

	}	

	if( i == high ){

		p->right = NULL;

	}else{

		secondOptimal(&(p->right), seq, sw, i+1, high);

	}



}



void printTree(BinaryTree *T){

	if(T == NULL){

		return;

	}

	printf(" %c", T->key );

	printf("(");

	if(T->left != NULL){

		printTree(T->left);

	}

	printf(",");

	if(T->right != NULL){

		printTree(T->right);

	}

	printf(")");

}



void main()

{

	int seq[] = { 0,  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'}; 

	float w[] = { 0,   1 ,  1 ,  2 ,  5 ,  3 ,  4 ,  4 ,  3 ,  5 };

	float *sw;

	int n = sizeof(seq)/sizeof(int);

	int i;

	BinaryTree *T = NULL;

	sw = (float *)malloc(sizeof(float) * n);



	/* Create the sum weight, sw[0] = 0; */

	sw[0] = 0;

	for(i=1; i<=n; i++){

		sw[i] = sw[i-1] + w[i];

	}



	printf("Original data:\n");

	for (i=0; i<n; i++) {

		printf("%c\t", seq[i]);

	}	

	printf("\n");

	for (i=0; i<n; i++) {

		printf("%02.2f\t", w[i]);

	}	

	printf("\n");



	for (i=0; i<n; i++) {

		printf("%02.2f\t", sw[i]);

	}	

	printf("\n");





	printf("Create second optimal tree:\n");

	secondOptimal(&T, seq, sw, 1, n-1); 



	printf("Print the tree:\n");

	printTree(T);

	printf("\n");





}