二叉搜索树操作~
失眠~敲代码~
程序代码：#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<conio.h>
struct node
{
int value;
struct node* left;
struct node* right;
};
typedef struct node NODE;
typedef struct node* PNODE;
void menu(); //菜单
int my_scanf(); //输入函数
void new_node(PNODE* n,int value); //创造一个新节点
void free_node(PNODE* n); //释放节点
void free_tree(PNODE* n); //释放二叉树
PNODE find_node(PNODE n,int value); //查找节点
void insert_node(PNODE* n,int value); //插入节点
int get_max_depth(PNODE n); //最长位置
int get_min_depth(PNODE n); //最短位置
int get_num_nodes(PNODE n); //获取节点数目
int get_min_value(PNODE n); //最短路径长度
int get_max_value(PNODE n); //最长路径长度
void deletenode(PNODE* n); //删除节点
void delete_node(PNODE* n,int value);
void pre_order_traversal(PNODE n); //前序遍历
void in_order_traversal(PNODE n); //中序遍历
void post_order_traversal(PNODE n); //后序遍历
int main()
{
int option=0;
PNODE tree=NULL;
PNODE node=NULL;
while (1)
{
system("cls");
menu();
option=my_scanf();
puts("---------------------------------");
if (option<0||option>11)
{
fprintf(stderr,"invalid option\n");
system("pause");
continue ;
}
switch (option)
{
case 0:
exit(0);
case 1:
printf("Enter number to inserrt:");
option=my_scanf();
puts("\n");
insert_node(&tree,option);
break;
case 2:
printf("Enter number to delete:");
option=my_scanf();
puts("\n");
delete_node(&tree,option);
break;
case 3:
printf("Enter number to find");
option=my_scanf();
puts("\n");
node=find_node(tree,option);
if (node!=NULL)
puts("Found node\n");
else
puts("Couldn't find node\n");
break;
case 4:
puts("Pre order traversal:");
pre_order_traversal(tree);
puts("\n");
break;
default :
break;
case 5:
puts("In order traversal:");
in_order_traversal(tree);
puts("\n");
break;
case 6:
puts("Post order traversal:");
post_order_traversal(tree);
puts("\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));
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;
}
system("pause");
}
return 0;
}
void menu()
{
puts("---------------------------------");
puts("0 Exit");
puts("1 Insert node");
puts("2 Delete node");
puts("3 Find node");
puts("4 Pre order traversal");
puts("5 In order traversal");
puts("6 Post order traversal");
puts("7 Max depth");
puts("8 Min depth");
puts("9 Max value");
puts("10 Min value");
puts("11 Node Count\n");
puts("---------------------------------");
printf("Select an option:");
}
int my_scanf()
{
char buf[50]={0};
int option=0;
fgets(buf,sizeof (buf),stdin);
sscanf(buf,"%i",&option);
return option;
}
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); //释放节点
*n=NULL;
}
PNODE find_node(PNODE n,int value) //查找节点
{
if (n==NULL) //如果节点为空则返回
return NULL;
if (n->value==value) //如果找到数据,则返回该数据的指针
return n;
if (value<=n->value)
return find_node(n->left,value);
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<(*n)->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=get_max_depth(n->left)+1;
if (n->right!=NULL)
right=get_max_depth(n->right)+1;
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=get_min_depth(n->left)+1;
if (n->right!=NULL)
right=get_min_depth(n->right)+1;
return (left<right?left:right);
}
int get_num_nodes(PNODE n) //获取节点数目
{
int left=0;
int right=0;
if (n==NULL)
return 0;
if (n->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;
return get_min_value(n->left);
}
int get_max_value(PNODE n) //最大路径长度
{
if (n==NULL)
return 0;
if (n->right==NULL)
return n->value;
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=NULL;
if ((*n)==NULL)
return ;
node=find_node(*n,value);
if ((*n)->value==value)
deletenode(n);
else if (value<(*n)->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);
}
}
