已知二叉树的先序序列,怎么建立二叉树并求其叶子结点和深度???~_百度...
发布网友
发布时间：2024-01-07 04:38
共2个回答
热心网友
时间：2024-07-27 23:09
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct Node
{
char data;
Node*left_tree;
Node*right_tree;
}RootNode;
RootNode*CreateBinTree() //创建二叉树
{
char ch;
scanf("%c",&ch);
if (ch==',')
{
return NULL;
}
RootNode*t=(Node*)malloc(sizeof(Node));
t->data=ch;
t->left_tree=CreateBinTree();
t->right_tree=CreateBinTree();
return t;
}
void InTraBinTree(RootNode*T) //中序遍历二叉树
{
if (NULL!=T->left_tree)
{
InTraBinTree(T->left_tree);
}
printf("%c",T->data);
if (NULL!=T->right_tree)
{
InTraBinTree(T->right_tree);
}
}
void PoTraBinTree(RootNode*T) //后序遍历二叉树
{
if (NULL!=T->left_tree)
{
InTraBinTree(T->left_tree);
}
if (NULL!=T->right_tree)
{
InTraBinTree(T->right_tree);
}
printf("%c",T->data);
}
int GetLeavesCounts(RootNode*T) //获得叶子结点个数
{
int counts=0; //记录叶子结点个数
if (NULL==T->left_tree && NULL==T->right_tree)
{
return 1;
}
if (NULL!=T->left_tree)
{
counts+=GetLeavesCounts(T->left_tree);
}
if (NULL!=T->right_tree)
{
counts+=GetLeavesCounts(T->right_tree);
}
return counts;
}
int GetBinTreeDeep(RootNode*T) //获得二叉树深度
{
if (NULL==T->left_tree && NULL==T->right_tree)
{
return 1;
}
int left_deep=0,right_deep=0;
if (NULL!=T->left_tree)
{
left_deep=GetBinTreeDeep(T->left_tree); //获得左子树的深度
}
if (NULL!=T->right_tree)
{
right_deep=GetBinTreeDeep(T->right_tree); //获得右子树的深度
}
if (left_deep>right_deep)
{
return left_deep+1;
}
return right_deep+1;
}
void DestroyBinTree(RootNode*T) //销毁二叉树
{
if (NULL==T->left_tree && NULL==T->right_tree)
{
free(T);
return;
}
if (NULL!=T->left_tree)
{
DestroyBinTree(T->left_tree);
}
if (NULL!=T->right_tree)
{
DestroyBinTree(T->right_tree);
}
free(T);
}
void main()
{
system("color 0a");
printf("输入一个长度小于50个字符的字符串:");
RootNode*BinTree=CreateBinTree(); //创建二叉树
InTraBinTree(BinTree); //中序遍历
printf("\n");
PoTraBinTree(BinTree); //后序遍历
printf("\n");
printf("%d\n",GetLeavesCounts(BinTree)); //输出叶子结点个数
printf("%d\n",GetBinTreeDeep(BinTree)); //输出二叉树深度
DestroyBinTree(BinTree); //销毁二叉树
system("pause");
}
专门为你编的，若还有疑问请加QQ：2609135351
热心网友
时间：2024-07-27 23:14
