create_t.cpp

一些关于数据结构的C语言实现源码

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define	NODENUMBER	11

enum{
	ROOT_FIRST,
	ROOT_MIDDLE,
	ROOT_LAST,
};

struct treenode{
  int value;
  struct treenode * left;
  struct treenode * right;
};

int root_first_array[NODENUMBER] =
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int root_middle_array[NODENUMBER] =
{3, 2, 5, 4, 1, 7, 9, 8, 11, 10, 6 };

int next_pos;
struct treenode *root;
int find_position( int root, int *array );

struct treenode * create_tree( int* first_array, int* middle_array, int size )
{
  int new_first_left_array[NODENUMBER];
  int new_middle_left_array[NODENUMBER];
  int new_first_right_array[NODENUMBER];
  int new_middle_right_array[NODENUMBER];

  int root_position, i, leftsize, rightsize;
  struct treenode *p;

  if( size == 0 ) return NULL;

  root_position = find_position( first_array[0], middle_array );
  if (root_position == -1){
	printf( "Searching error!\n" );
	return NULL;
  }
//  printf( "Search position of %d at %d.\n", first_array[0], root_position );
//  getch();

  p = (struct treenode*) malloc( sizeof(struct treenode) );
  p -> value = first_array[0];

  for( i=1; i<=root_position; i++ )	//left half
    new_first_left_array[i-1] = first_array[i];
  for( i=0; i<root_position; i++)
    new_middle_left_array[i] = middle_array[i];
  leftsize = root_position;
  p->left = create_tree( new_first_left_array, new_middle_left_array, leftsize );

  for( i=root_position+1; i<size; i++ )	//right half
    new_first_left_array[i-root_position-1] = first_array[i];
  for( i=root_position+1; i<size; i++)
    new_middle_left_array[i-root_position-1] = middle_array[i];
  rightsize = size - root_position - 1;
  p->right = create_tree( new_first_left_array, new_middle_left_array, rightsize );

  return p;
}

//used to find the position of root in the array,
//	-1: not find
int find_position( int root, int *array )
{
  int i;
  for ( i=0; i<NODENUMBER; i++ )
      if( array[i] == root ) return i;
  return -1;
}

void travel( struct treenode * root, int method )
{
  if (root == NULL ) return;
  if ( method == ROOT_FIRST ) printf( "Node %d is visited.\n", root->value );
  travel( root->left, method );
  if ( method == ROOT_MIDDLE ) printf( "Node %d is visited.\n", root->value );
  travel( root->right, method );
  if ( method == ROOT_LAST ) printf( "Node %d is visited.\n", root->value );
}


void main()
{
  clrscr();
  root = create_tree( root_first_array, root_middle_array, NODENUMBER );
  travel( root, ROOT_FIRST );
}