tree.cpp

求二叉树深度与节点数的集合

#include <stdlib.h>
#include <stdio.h>
#define OK 1
#define OVERFLOW -2
typedef struct BinNode			/*定义二叉树结构*/
{  
	char data;
	struct BinNode	*lchild,*rchild;
} BinNode, *BinTree;

int CreateBinTree(BinTree *Tree)
{
	char ch;
	scanf("%c",&ch);
	if(ch == '.') 
		(*Tree) = NULL;
	else
	{
		if(!((*Tree) = (BinTree)malloc(sizeof(BinNode)))) 
			exit(OVERFLOW);
		(*Tree)->data = ch;
		CreateBinTree(&((*Tree)->lchild));
		CreateBinTree(&((*Tree)->rchild));
	}
	return (OK); 
}/*CreateBiTree*/

int depth(BinTree T)
{
	int n,n1,n2;
	if(!T)
		n=0;
	else
	{
		n1=depth(T->lchild);
		n2=depth(T->rchild);
		n=1+(n1>n2?n1:n2);
	}
	return n;
}

int  leaf(BinTree T)
{
    int n1,n2;
	if(!T) return 0;
	else if((!T->lchild) &&  (!T->rchild))return 1;
	else
	{
		 n1=leaf(T->lchild);
		 n2=leaf(T->rchild);
		 return(n1+n2);
	}
}

void main()		
{  
	BinTree T=NULL;
	printf("请输入您要建立的二叉树的先序扩展序列(用.表示空)\n");

	CreateBinTree(&T);			
	printf("构造二叉树成功!\n");
    printf("您所输的二叉树的高度为：");
	printf("%d\n",depth(T));
	printf("您所输的二叉树所含叶子节点数为：");
	printf("%d\n",leaf(T));
}