二叉树的常见操作编写程序用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...全部
#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();
}
。
收起
