#include"malloc.h"
#define NULL 0
#include"stdio.h"
typedef struct node
{
char data;
struct node *lchild,*rchild;
}NODE;
int count;
NODE *crt_bt_pre()/*二叉树先序创建算法*/
{
NODE * bt;
char ch;
printf("\n\t\t\t");
scanf("%c",&ch);
getchar();
if(ch==' ') bt=NULL;
else
{
bt=(NODE*)malloc(sizeof(NODE));
bt->data=ch;
printf("\n\t\t\t请输入%c结点的左孩子:",bt->data); bt->lchild=crt_bt_pre();
printf("\n\t\t\t请输入%c结点的右孩子:",bt->data); bt->rchild=crt_bt_pre();
}
return(bt);
}
void Preorder(NODE* bt)/*二叉树先序递归遍历算法*/ {
if(bt!=NULL)
{
printf("\n\t\t\t %c",bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
void Inorder(NODE* bt)
{
if(bt!=NULL)
{
Inorder(bt->lchild);
printf("\n\t\t\t %c",bt->data);
Inorder(bt->rchild);
}
}
void Postorder(NODE* bt)
{
if(bt!=NULL)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("\n\t\t\t %c",bt->data);
}
}
int CountLeaf(NODE *bt)/*求二叉树叶子结点数的递归遍历算法*/ {
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL)
count++;
CountLeaf(bt->lchild);
CountLeaf(bt->rchild);
return(count);
}
int CountNode (NODE* bt)/*求二叉树结点数的递归遍历算法*/ {
if(bt==NULL)
return 0;
else
count++;
CountNode(bt->lchild);
CountNode(bt->rchild);
return(count);
}
int TreeDepth(NODE* bt)/*求二叉树深度的递归遍历算法*/ {
int x,y;
if(bt==NULL)
return 0;
else
x=TreeDepth(bt->lchild);
y=TreeDepth(bt->rchild);
if(x>y)
return(x+1);
else
return(y+1);
}
void main()
{
NODE *bt;
char choice;
int j=1;
int x;
while(j)
{
printf("\n\n\n");
printf("\t\t\t-二叉树的基本运算--\n");
printf("\n\t\t\t************************************");
printf("\n\t\t\t* 1-------建二 差树 *");
printf("\n\t\t\t* 2-------先序 遍历 *");
printf("\n\t\t\t* 3-------中序 遍历 *");
printf("\n\t\t\t* 4-------后序 遍历 *");
printf("\n\t\t\t* 5-------统计 叶子数 *");
printf("\n\t\t\t* 6-------统计 结点数 *");
printf("\n\t\t\t* 7-------求二叉树深度 *");
printf("\n\t\t\t* 0-------退 出 *");
printf("\n\t\t\t************************************");
printf("\t\t\t请选择菜单号(0--7):");
scanf("%c",&choice);getchar();
if(choice=='1')
{
printf("\n\t\t\t请输入按先序建立二叉树的结点序列: ");
printf("\n\t\t\t说明: 逐个输入,输入空格代表后续结点为空,按回车输入下一个结点.");
printf("\n\t\t\t请输入根结点: ");
bt=crt_bt_pre();
printf("\n\t\t\t二叉树成功建立!\n");
}
else if(choice=='2')
{ printf("\n\t\t\t该二叉树的先序遍历序列为: "); Preorder(bt); } else if(choice=='3') { printf("\n\t\t\t该二叉树的中序遍历序列为: "); Inorder(bt); } else if(choice=='4') { printf("\n\t\t\t该二叉树的后序遍历序列为: "); Postorder(bt); } else if(choice=='5') { count=0; CountLeaf(bt); printf("\n\t\t\t该二叉树有%d个叶子结点。\n",count); } else if(choice=='6') { count=0; x=CountNode(bt); printf("\n\t\t\t该二叉树共有%d个叶子结点。\n",count); } else if(choice=='7') { x=TreeDepth(bt); printf("\n\t\t\t该二叉树的深度为%d",x); } else if(choice=='0') { j=0; printf("\t\t\t程序结束!\n"); }
}
}
第二篇：求二叉树的深度
#include<stdio.h>#include<malloc.h>#define NULL 0typedef struct ECshu{struct ECshu *lchild;struct ECshu *rchild;char data;}*linkecshu;linkecshu Creatshu(linkecshu &root){char s1;scanf("%c",&s1);if (s1==' ') root=NULL;else{if((root=(linkecshu)malloc(sizeof(struct ECshu)))) {root->data=s1;Creatshu(root->lchild);Creatshu(root->rchild);}}return root;}void Printecshu(linkecshu &root)//这里肯定没有错误。{if(root){Printecshu(root->lchild);printf("%c",root->data);Printecshu(root->rchild);}}int Depth(linkecshu root)// 返回二叉树的深度{ int depthval,depthLeft,depthRight;if ( !root) depthval = 0;else {depthLeft = Depth( root->lchild );depthRight= Depth( root->rchild );depthval =1+(depthLeft > depthRight ?depthLeft : depthRight);} return depthval;}void main(){linkecshu r,h;int sd;printf("请输入您要建立的二叉树的各项数据元素:\n");h=Creatshu(r);printf("您输入的二叉树为:\n");Printecshu(h);printf("\n");sd=Depth(r);printf("二叉树深度为%d",sd);getchar();getchar();}