c语言输入一个二叉树序列,二叉树的常见操作

#include

#include

#include

struct node

{

int value;

struct node* left;

struct node* right;

};

typedef struct node NODE;

typedef struct node* PNODE;

void new_node(PNODE* n,int value)

{

*n=(PNODE)malloc(sizeof(NODE));

if(*n!=NULL)

{

(*n)->value=value;

(*n)->left=NULL;

(*n)->right=NULL;

}

}

void free_node(PNODE* n)

{

if((*n)!=NULL)

{

free(*n);

*n=NULL;

}

}

void free_tree(PNODE* n)

{

if(*n==NULL)return;

if((*n)->left!=NULL)

{

free_tree(&((*n)->left));

}

if((*n)->right!=NULL)

{

free_tree(&((*n)->right));

}

free_node(n);

}

PNODE find_node(PNODE n,int value)

{

if(n==NULL)

{

return NULL;

}

else if(n->value==value)

{

return n;

}

else if(value value)

{

return find_node(n->left,value);

}

else

{

return find_node(n->right,value);

}

}

void insert_node(PNODE* n,int value)

{

if(*n==NULL)

{

new_node(n,value);

}

else if(value==(*n)->value)

{

return;

}

else if(value value)

{

insert_node(&((*n)->left),value);

}

else

{

insert_node(&((*n)->right),value);

}

}

int get_max_depth(PNODE n)

{

int left=0;

int right=0;

if(n==NULL)

{

return 0;

}

if(n->left!=NULL)

{

left=1+get_max_depth(n->left);

}

if(n->right!=NULL)

{

right=1+get_max_depth(n->right);

}

return(left>right?left:right);

}

int get_min_depth(PNODE n)

{

int left=0;

int right=0;

if(n==NULL)

{

return 0;

}

if(n->left!=NULL)

{

left=1+get_min_depth(n->left);

}

if(n->right!=NULL)

{

right=1+get_min_depth(n->right);

}

return (left left!=NULL)

{

left=get_num_nodes(n->left);

}

if(n->right!=NULL)

{

right=get_num_nodes(n->right);

}

return(left+1+right);

}

int get_min_value(PNODE n)

{

if(n==NULL) return 0;

if(n->left==NULL)

{

return n->value;

}

else

{

return get_min_value(n->left);

}

}

int get_max_value(PNODE n)

{

if(n==NULL)return 0;

if(n->right==NULL)

{

return n->value;

}

else

{

return get_max_value(n->right);

}

}

void deletenode(PNODE* n)

{

PNODE tmp=NULL;

if(n==NULL) return;

if((*n)->right==NULL){

tmp=*n;

*n=(*n)->left;

free_node(n);

}

else if((*n)->left==NULL)

{

tmp=*n;

*n=(*n)->right;

free_node(n);

}

else

{

for(tmp=(*n)->right;tmp->left!=NULL;tmp=tmp->left);

tmp->left=(*n)->left;

tmp=(*n);

*n=(*n)->right;

free_node(&tmp);

}

}

void delete_node(PNODE* n,int value)

{

PNODE node;

if(n==NULL) return;

node=find_node(*n,value);

if((*n)->value==value)

{

deletenode(n);

}

else if(value value)

{

delete_node(&((*n)->left),value);

}

else

{

delete_node(&((*n)->right),value);

}

}

void pre_order_traversal(PNODE n)

{

if(n!=NULL)

{

printf("%i",n->value);

pre_order_traversal(n->left);

pre_order_traversal(n->right);

}

}

void in_order_traversal(PNODE n)

{

if(n!=NULL)

{

in_order_traversal(n->left);

printf("%i",n->value);

in_order_traversal(n->right);

}

}

void post_order_traversal(PNODE n)

{

if(n!=NULL)

{

post_order_traversal(n->left);

post_order_traversal(n->right);

printf("%i",n->value);

}

}

void main()

{

char buf[50];

int option;

PNODE tree=NULL;

PNODE node=NULL;

while(1)

{

printf("-------------------\n");

printf("Options are:\n\n");

printf("0 Exit\n");

printf("1 Insert node\n");

printf("2 Delete node\n");

printf("3 Find node\n");

printf("4 Pre order traversal\n");

printf("5 In order traversal\n");

printf("6 Post order traversal\n");

printf("7 Max depth\n");

printf("8 Min depth\n");

printf("9 Max value\n");

printf("10 Min value\n");

printf("11 Node Count\n\n");

printf("-------------------\n");

printf("Select an option:");

fgets(buf,sizeof(buf),stdin);

sscanf(buf,"%i",&option);

printf("-------------------\n");

if(option 11)

{

fprintf(stderr,"Invalid option");

continue;

}

switch(option)

{

case 0:

exit(0);

case 1:

printf("Enter number to insert:");

fgets(buf,sizeof(buf),stdin);

sscanf(buf,"%i",&option);

printf("\n\n");

insert_node(&tree,option);

break;

case 2:

printf("Enter number to delete:");

fgets(buf,sizeof(buf),stdin);

sscanf(buf,"%i",&option);

printf("\n\n");

delete_node(&tree,option);

break;

case 3:

printf("Enter number to find:");

fgets(buf,sizeof(buf),stdin);

sscanf(buf,"%i",&option);

printf("\n\n");

node=find_node(tree,option);

if(node!=NULL)

{

printf("FOUND node\n\n");

}

else

{

printf("Couldn't find node\n\n");

}

break;

case 4:

printf("Pre order traversal:");

pre_order_traversal(tree);

printf("\n\n");

break;

case 5:

printf("In order traversal:");

in_order_traversal(tree);

printf("\n\n");

break;

case 6:

printf("Post order traversal:");

post_order_traversal(tree);

printf("\n\n");

break;

case 7:

printf("Max depth is %i\n\n",get_max_depth(tree));

break;

case 8:

printf("Min depth is %i\n\n",get_min_depth(tree));

break;

case 9:

printf("Max value is %i\n\n",get_max_value(tree));

break;

case 10:

printf("Min value is %i\n\n",get_min_value(tree));

break;

case 11:

printf("Node Count is %i\n\n",get_num_nodes(tree));

break;

}

}

printf("Press Anykey to End the Program!");

getch();

}

。

全部