苗火 Nicholas

[Data structures]Second optimal search tree

2019-7-5 萧 写技术

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


}

标签: Data Structures data_structures