要求:按先序序列输入一些字母,建立一个二叉树,然后按中序输出个结点的字母,再求出树的高度和叶子结点数并打印叶子结点。
如输入:abc##de#g##f###
中序输出为cbegdfa
#include<stdio.h>
#include<malloc.h>
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode;//结点定义
//BiTree root;//根结点定义
//构造二叉树
Status BiTree CreateBiTree(BiTree &T){
//按先序输入个接点的值,空格字符#表示空树
//构造二叉链表表示的二叉树T
char ch;
printf("输入接点字符");
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))return ERROR;
T->data=ch;//生成根接点
CreateBiTree(T->lchild); //构造左子树
CreateBiTree(T->rchild); //构造右子树
}
return T;
}//CreateBinTree
//中序访问并输出各接点字符
Status INORDER(BiTree *T){
if(T)
{INORDER(T->lchild); //中序遍历左子树
printf("\t%c\n",T->data); //访问接点*t
INORDER(T->rchild); //中序遍历右子树
}
}
//计算树的高度
int depth(BiTree T){
int dep1,dep2;
if(T==NULL)return(0);
else
{dep1=depth(T->lchild);
dep2=depth(T->lchild);
if(dep1>dep2)return(dep1+1);
else return(dep2+1);}
}
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数
}//LeafCount_BiTree
void main(){
BiTree root;/*根结点指针定义*/
CreateBiTree(&root);/*传入根结点指针的地址在函数中指向二叉树根*/
INORDER(root);
depth(BiTree T)
LeafCount_BiTree(Bitree T)
}
眼眸繁星
大话西游666