download1.txt

二叉树叶子结点计算

// Tree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "malloc.h"
#include "stdio.h"
#define OK 1
#define OVERFLOW 0

typedef char TElemType;
typedef int Status;
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode *parent, *lchild, *rchild; 
                              // 左右孩子指针
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T) {
	char ch;

    scanf("%c",&ch);
    if (ch==' ') T = NULL;
    else {
      if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
        return (OVERFLOW);
      T->data = ch;              // 生成根结点
	    

      CreateBiTree(T->lchild);   // 构造左子树
      CreateBiTree(T->rchild);   // 构造右子树
    }
    return OK;
} // CreateBiTree

void Preorder (BiTree T)
{ // 先序遍历二叉树 
	int i=0;
   if (T) {
      printf("%c",T->data);            // 访问结点
	 
      Preorder(T->lchild); // 遍历左子树
      Preorder(T->rchild);// 遍历右子树
	  

   }
  
}

void Inorder (BiTree T)
{ // 中序遍历二叉树 
   if (T) {
      Inorder(T->lchild); // 遍历左子树
      printf("%c",T->data);            // 访问结点
      Inorder(T->rchild);// 遍历右子树
	 
   }
}
 
void aftorder (BiTree T)
{if(T){
aftorder(T->lchild);
aftorder(T->rchild);
printf("%c",T->data);}
}


void CountLeaf(BiTree T, int& count){
   if ( T ) {
      if ((!T->lchild)&& (!T->rchild))
         count++;     // 对叶子结点计数
      CountLeaf( T->lchild, count);  
      CountLeaf( T->rchild, count); 
   } // if
  
} // CountLeaf
int depthval ,depthLeft,depthRight;
int Depth (BiTree T )
{ // 返回二叉树的深度

   if ( !T )    depthval = 0;
   else   {
     depthLeft = Depth( T->lchild );
	 
     depthRight= Depth( T->rchild );
     
     depthval = 1 + (depthLeft > depthRight  ?
                               depthLeft : depthRight);
   } 
   
  return depthval;
}



int main(int argc, char* argv[])
{   int count=0 ;
	BiTree T;
	CreateBiTree(T);
	Preorder(T);
    printf("\n");
    Inorder(T);
	printf("\n");
	aftorder(T);
	printf("\n");
	CountLeaf(T, count);
    printf("%d",count);
	printf("\n");
    Depth (T);
    printf("%d",depthval);
    printf("\n");
	return 0;
}