countleafdepth.cpp

文件夹中包括常用的数据结构的算法

#include<malloc.h>
#include <stdio.h>
#define m0 100   //定义字符串结构中的最大长度
#define m2 20
#define null 0
#define Len  sizeof (BinNode)

enum tag{zero,one};

typedef struct BinNode             // 结点结构
{ 
	char data;
    struct BinNode *lch,*rch;
    enum tag ltag,rtag;
}BinNode,*Bintree;


struct chtp{ int len;      char ch[m0];    };  //定义字符串结构
struct BinNode *bt;   //定义2叉树的根节点指针
struct BinNode *stack[m2];       //定义堆栈，中序遍历二叉树的非递归算法要用
struct chtp s;
int top=0,ii=0;          //两个全局变量

void  crt_pre(Bintree *t) 
{ 
	char c;
    c=s.ch[ii];  
	ii=ii+1;

    if (c=='.')  *t=null;
    else 
	{ 
		*t=(BinNode *)malloc(Len);
		(*t)->data=c;
		crt_pre(&(*t)->lch);
		crt_pre(&(*t)->rch);
    };
}

int CountLeaf (BinNode *T) 
{
    if (T==NULL)  return 0;
    else if (T->lch==NULL && T->rch==NULL)  return 1;
    else  return  CountLeaf(T->lch) + CountLeaf(T->rch);
}


int Depth (BinNode *T )
{      // 返回二叉树的深度
	int  depthval;
   if ( !T )    depthval = 0;
   else
   { 
	   int depthLeft = Depth( T->lch );
       int depthRight= Depth( T->rch );
       depthval = 1 + (depthLeft > depthRight  ? depthLeft : depthRight);
   } 
   return depthval;
}



void main()
{
//	char /*c[]={'a','b','d','.','.','.','c','e','.','.','f','.','.','!'};*/
    char    c[]={'a','b','c','.','.','d','e','.','g','.','.','f','.','.','.','!'};
    int i=0;
    for(i=0,s.len=0;c[i]!='!';i++,s.len++) s.ch[i]=c[i];
    
	crt_pre(&bt);


	printf("the num of leaf is %d \n", CountLeaf(bt));
	printf("the depth is %d \n", Depth(bt));

}