#include<stdlib.h>
#include<assert.h> //方便使用断言
//#define empty '#' //定义空节点
#define TREE_TYPE int //定义树的类型
#define TREE_DATE char //表中存储值的类型
static TREE_TYPE cout_leves=0; //叶子节点的个数，定义为全局变量，防止二次操作时，上次的值影响。
static TREE_TYPE depth_tree=0; //保存计算树的深度
//定义链式的二叉树结构
typedef struct TREE_NODE{
char value;
struct TREE_NODE *left;//定义左孩子节点
struct TREE_NODE *right;//定义右孩子节点
}TreeNode;
//初始化二叉树
void init_tree(TreeNode **tree)
{
*tree=NULL;
return;
}
//建立链式的二叉树
//以先序方式建立
void creat_binTree(TreeNode **tree)
{
char ch;
if((ch=getchar())=='#')
*tree=NULL;
else
{
*tree=(TreeNode *)malloc(sizeof(TreeNode));
if(*tree==NULL)
{
printf("二叉树建立失败，请重新建立！\n");
exit(EXIT_FAILURE);
}
(*tree)->value=ch;
creat_binTree(&((*tree)->left));
creat_binTree(&((*tree)->right));
}
}
//释放树空间
void delete_tree(TreeNode *tree)
{
if(tree!=NULL)
{
delete_tree(tree->left);
delete_tree(tree->right);
free(tree);
}
}
//向二叉树中插入值
//插入的是二叉树中没有的值
void insert_value(TreeNode *tree,TREE_TYPE value)
{
TreeNode *current;
TreeNode **link;
link=&tree; //link指向创建的树，从根节点开始
while((current=*link)!=NULL&&value!=current->value) //比较操作
{
if(value<current->value)
link=¤t->left;
else
link=¤t->right;
}
//分配一个新的节点
current=(TreeNode *)malloc(sizeof(TreeNode));
if(current==NULL)
{
printf("分配节点失败！\n");
exit(EXIT_FAILURE);
}
else
{
current->value=value;
current->left=NULL;
current->right=NULL;
*link=current;
}
}
//在二叉树中实行查找操作
//TREE_TYPE
void find_value(TreeNode *tree,TREE_TYPE value)
{
TreeNode *link;
link=tree; //存放树的根节点
//查找
while(link!=NULL&&link->value!=value)
{
if(value<link->value)
link=link->left;
else
link=link->right;
}
//如果没到结尾已查到
if(link!=NULL)
printf("已找到!");
//return current->value;
else
printf("没找到该查找的值!");
}
//删除树的一个节点
void delete_node_tree( TreeNode *tree, TREE_DATE value )
{
TreeNode *current ; //保存需要删除的点
TreeNode **link ;
link = &tree ;
while( ( current = *link )!= NULL && value != current->value) //得出需要删除的点
{
if( value< tree->value )
link = ¤t->left ;
else
link = ¤t->right ;
}
assert( current != NULL ) ; //断言
if( current->left == NULL && current->right == NULL) //当前点是叶子节点，直接删除
{
*link = NULL ;
free( current ) ;
}
else if(current->left == NULL || current->right == NULL) //当前点只有一个孩子节点，用孩子节点充当当前节点
{
if( current->left != NULL )
*link = current->left ;
else
*link = current->right ;
}
//当前节点有两个孩子，他不能连接两个孩子，解决的办法是不删除这个节点，而是删除他的左子树中最大的那个节点，
//并用这个值代替原先应被删除的那个点的值。
else
{
TreeNode *this_node ;
TreeNode *next_node ;
this_node = current->left ;
next_node = this_node->left ;
while( next_node != NULL )
{
this_node = next_node ;
next_node = this_node->left;
}
value = this_node->value ;
delete_node_tree( this_node, value ) ;
current->value = value ;
}
}
//实现前序遍历
void pre_order_traverse(TreeNode *tree)
{
if(tree!=NULL)
{
printf("%c",tree->value);
pre_order_traverse(tree->left);
pre_order_traverse(tree->right); //前序遍历:节点->左子树->右子树
}
}
//实现中序遍历
void in_order_traverse(TreeNode *tree)
{
if(tree!=NULL)
{
in_order_traverse(tree->left);
printf("%c",tree->value);
in_order_traverse(tree->right); //前序遍历:左子树->节点->右子树
}
}
/* 非递归的中序遍历*/
void iin_order_traverse(TreeNode *tree)
{
TreeNode *current;
TreeNode *stack[100]; //定义了一个栈对象
TREE_TYPE top=0;
stack[top++]=tree;
while(top>0)
{
current=stack[top-1];
while(current!=NULL)
{
stack[top++]=current->left;
current=stack[top-1];
}
//空指针退栈
current=stack[--top];
if(top>0)
{
current=stack[--top];
printf("%c",current->value);
stack[top++]=current->right;
}
}
}
//实现后序遍历
void rear_order_traverse(TreeNode *tree)
{
if(tree!=NULL)
{
rear_order_traverse(tree->left);
rear_order_traverse(tree->right); //前序遍历:左子树->右子树->节点
printf("%c",tree->value);
}
}
//求树的深度
TREE_TYPE deep_tree(TreeNode *tree)
{
TREE_TYPE ldepth_tree=0;
TREE_TYPE rdepth_tree=0;
if(tree==NULL)
return 0;
if(tree!=NULL)
{
ldepth_tree=deep_tree(tree->left);
rdepth_tree=deep_tree(tree->right);
depth_tree=(ldepth_tree>rdepth_tree)?(ldepth_tree+1):(rdepth_tree+1);
}
return depth_tree;
}
//树的叶子节点个数
TREE_TYPE leves_tree(TreeNode *tree)
{
if(tree==NULL)
return 0;
if(tree->left==NULL&&tree->right==NULL)
cout_leves+=1;
else
{
leves_tree(tree->left);
leves_tree(tree->right);
}
return cout_leves;
}
//树的叶子节点
void levenode_tree(TreeNode *tree)
{
if(tree==NULL)
return;
if(tree->left==NULL&&tree->right==NULL)
putchar(tree->value); //输出叶子节点
else
{
levenode_tree(tree->left);
levenode_tree(tree->right);
}
}
//计算二叉树的节点数量
TREE_TYPE count_nodes(TreeNode *tree)
{
if(tree==NULL)
return 0;
return 1+count_nodes(tree->left)+count_nodes(tree->right);
}
//按层次遍历二叉树
//操作的选择菜单
void menu_tree()
{
printf("\n\n");
printf("\t*********请选择您需要的操作*********\n");
printf("\t\t1.创建二叉树\n");
printf("\t\t2.插入一个节点\n");
printf("\t\t3.查找一个节点\n");
printf("\t\t4.删除一个节点\n");
printf("\t\t5.层次遍历\n");
printf("\t\t6.前序遍历\n");
printf("\t\t7.中序遍历\n");
printf("\t\t8.后序遍历\n");
printf("\t\t9.叶子节点\n");
printf("\t\t10.树的深度\n");
printf("\t\t11.节点个数统计\n");
printf("\t\t12.退出系统\n");
printf("\t***********欢迎使用本系统***********\n");
}
//选择需要的操作
void sys_select(void)
{
int TRUE=1 ; //控制结束设置的
TREE_TYPE count ; //二叉树的节点数量统计
TreeNode *BinTree ;
TREE_DATE value ; //需要插入的值
TREE_DATE fvalue ; //需要查找的值
TREE_DATE dvalue ; //需要删除的节点
TREE_TYPE levenode=0 ; //叶子节点个数
int flag=0; //选择标致位
printf("\n");
printf("\t\t友情提示: 请先创建一个二叉树：\n");
while(TRUE)
{
//fflush(stdin);
printf("请输入操作代号->:");
start:
scanf("%d",&flag);
if(!(flag>=1&&flag<=12))
{
printf("请重新输入操作代号->:");
fflush(stdin);
goto start;
}
switch(flag)
{
//建立二叉树
case 1:
{
init_tree(&BinTree); //创建二叉树之前先初始化二叉树
fflush(stdin); //不加此句会出现错误，刷新缓冲区
creat_binTree(&BinTree);
printf("创建成功!\n\n");
}
break;
//插入值
case 2:
printf("请输入需要插入的值:\n");
fflush(stdin);
scanf("%c",&value);
insert_value(BinTree,value);
printf("插入成功!");
fflush(stdin);
printf("\n\n");
break;
//查找值
case 3:
printf("请输入需要查找的值:\n");
fflush(stdin);
scanf("%c",&fvalue);
find_value(BinTree ,fvalue); //在二叉树中实行查找操作
printf("\n\n");
break;
//删除一个节点
case 4:
printf("请输入需要删除的值:\n");
fflush(stdin);
scanf("%c",&dvalue);
delete_node_tree(BinTree,dvalue);
printf("\n\n");
break;
//实现层次遍历
case 5:
break;
//前序遍历
case 6:
pre_order_traverse(BinTree);
printf("\n\n");
break;
//中序遍历
case 7:
iin_order_traverse(BinTree);
printf("\n\n");
break;
//后序遍历
case 8:
rear_order_traverse(BinTree);
printf("\n\n");
break;
//叶子节点与个数
case 9:
cout_leves=0;
levenode=leves_tree(BinTree);
printf("叶子节点个数为:%d->",levenode);
levenode_tree(BinTree);
printf("\n\n");
break;
//树的深度
case 10:
printf("深度为:->%d",deep_tree(BinTree));
printf("\n\n");
break;
//节点个数统计
case 11:
count=count_nodes(BinTree);
printf("节点个数为:->%d\n\n",count);
break;
//退出
case 12:
delete_tree(BinTree);
default:
TRUE=0;
break;
}
}
}
void main(void)
{
menu_tree();
sys_select();
}
1 个解决方案
#1
楼主啥问题？
#1
楼主啥问题？