treemain.bak

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

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

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

#define MAXVALUE 16
struct treenode *root;

int value_array[MAXVALUE];
int nextpos = 0;

int number_of_leaves = 0;	//used to calculate the number of leaves
int maxdepth = 0;        	//used to calculate the depth of the tree

int depth = 0;			//temperily record the travel depth

void create_treenode( struct treenode * );

int initalize()
{
  int i;

  for( i=0; i<MAXVALUE; i++ ) value_array[i] = i;

  root = (struct treenode *)malloc( sizeof(struct treenode) );
  root -> value = value_array[nextpos];
  root -> left = NULL;
  root -> right = NULL;
  nextpos++;
  create_treenode( root );
//  create_treenode2( root );
  return 0;
}

//build a very easy tree, so much nodes in the left
void create_treenode( struct treenode * parent)
{
  struct treenode *left, *right;

  if ( parent == NULL ) return;

  if ( nextpos > MAXVALUE ) return;
  left = (struct treenode *)malloc( sizeof( struct treenode ) );
  left -> value =value_array[nextpos];
  left -> left = NULL;
  left -> right = NULL;
  nextpos++;
  parent->left = left;

  if ( nextpos > MAXVALUE ) return;
  right = (struct treenode *)malloc( sizeof( struct treenode ) );
  right -> value =value_array[nextpos];
  right -> left = NULL;
  right -> right = NULL;
  nextpos++;
  parent->right = right;

  create_treenode( right );
  create_treenode( left );
  return;
}

void travel( struct treenode * root )
{
  //visit the root first, middle, last
  if (root == NULL ) return;

  depth ++;
  if (depth > maxdepth ) maxdepth = depth;

//  //THE following is the action of visiting
//  printf( "Node %d is visited.\n", root->value );
//  if ( (root->left == NULL)&&(root->right == NULL) )
//	number_of_leaves++;

  travel( root->left );

  travel( root->right );

  //THE following is the action of visiting
  printf( "Node %d is visited.\n", root->value );
  if ( (root->left == NULL)&&(root->right == NULL) )
	number_of_leaves++;

  depth --;
}

main()
{
  clrscr();
  initalize();
  travel( root );
  printf( "This tree has %d leaves.\n", number_of_leaves );
  printf( "The depth of the tree is%d.\n", maxdepth );
  return 0;
}