#include<stdlib.h>
#include <stdio.h>
typedef struct BiTNode
{
char data;
BiTNode *lchild,*rchild;
}BiTreeNode,*BiTree;
void CreateBiTree(BiTree &T) //按先序序列建立二叉树
{
char ch;
printf("输入二叉树结点的值:");
scanf("%c",&ch);
if(ch=='#')
{
T=NULL;
}
else
{
T=(BiTreeNode*)malloc(sizeof(BiTreeNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void inorder(BiTree T) //中序遍历二叉树,输出结点的值
{
if(T==NULL)
return;
else
{
inorder(T->lchild);
printf("%c\n",T->data);
inorder(T->rchild);
}
}
void postorder(BiTree T) //后序遍历二叉树,输出结点的值
{
if(T==NULL)
return;
else
{
postorder(T->lchild);
postorder(T->rchild);
printf("%c\n",T->data);
}
}
void CountLeaf(BiTree T,int &count) //统计叶子结点的个数
{
if(T)
{
if((T->lchild==NULL)&&(T->rchild==NULL))
count++;
CountLeaf(T->lchild,count);
CountLeaf(T->rchild,count);
}
}
int Depth(BiTree T) //求二叉树的深度
{
int depthval,depthLeft,depthRight;
if(!T)
depthval=0;
else
{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
main()
{
int count=0;
printf("先序建立二叉树:\n");
BiTree T;
CreateBiTree(T);
if(T==NULL)
printf("这是一棵空树!");
printf("\n中序输出建立的二叉树:\n");
inorder(T);
printf("\n后序输出建立的二叉树:\n");
postorder(T);
CountLeaf(T,count);
printf("\n这棵树共有%d个叶子结点\n",count);
printf("\n这棵树的深度是%d\n\n",Depth(T));
}
运行出来是这种结果,且输入完个结点的数据后,输入井号不能终止输入
代码没什么问题,建立二叉树的函数void CreateBiTree(BiTree &T) 里输入语句做个修改即可,见注释处,供参考:
#include<stdlib.h>
#include <stdio.h>
typedef struct BiTNode
{
char data;
BiTNode *lchild,*rchild;
}BiTreeNode,*BiTree;
void CreateBiTree(BiTree &T) //按先序序列建立二叉树
{
char ch;
printf("输入二叉树结点的值:");
scanf(" %c",&ch); //修改
//scanf("%c",&ch);
if(ch=='#')
{
T=NULL;
}
else
{
T=(BiTreeNode*)malloc(sizeof(BiTreeNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void inorder(BiTree T) //中序遍历二叉树,输出结点的值
{
if(T==NULL)
return;
else
{
inorder(T->lchild);
printf("%c\n",T->data);
inorder(T->rchild);
}
}
void postorder(BiTree T) //后序遍历二叉树,输出结点的值
{
if(T==NULL)
return;
else
{
postorder(T->lchild);
postorder(T->rchild);
printf("%c\n",T->data);
}
}
void CountLeaf(BiTree T,int &count) //统计叶子结点的个数
{
if(T)
{
if((T->lchild==NULL)&&(T->rchild==NULL))
count++;
CountLeaf(T->lchild,count);
CountLeaf(T->rchild,count);
}
}
int Depth(BiTree T) //求二叉树的深度
{
int depthval,depthLeft,depthRight;
if(!T)
depthval=0;
else
{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
int main()
{
int count=0;
printf("先序建立二叉树:\n");
BiTree T;
CreateBiTree(T);
if(T==NULL)
printf("这是一棵空树!");
printf("\n中序输出建立的二叉树:\n");
inorder(T);
printf("\n后序输出建立的二叉树:\n");
postorder(T);
CountLeaf(T,count);
printf("\n这棵树共有%d个叶子结点\n",count);
printf("\n这棵树的深度是%d\n\n",Depth(T));
return 0;
}
输入 ‘#’ 号不能终止的原因,是和你要创建的二叉树的结构有关,下面是建立两个不同的二叉树的运行结果抓图,供参考:
这样输入试试
1
2
#
#
3
#
#
你需要输入俩个#。
看你代码里有俩个递归调用,创建左子树,还有创建右子树。每一个子树都需要终止之后,create函数才执行结束。
void CreateBiTree(BiTree &T) //按先序序列建立二叉树
{
char ch;
printf("输入二叉树结点的值:");
scanf(" %c",&ch); //修改
//scanf("%c",&ch);
if(ch=='#')
{
T=NULL;
return;
}
else
{
T=(BiTreeNode*)malloc(sizeof(BiTreeNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}