erchashu.zip.cpp

有关二叉树的原代码 主要是求叶子节点数目 和前 中 后 序遍历

#include "stdio.h" 
#include "stdlib.h" 
#include "string.h" 
#define null 0 



#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define STACKINCREMENT 10

typedef int Status;
typedef int TElemType;

typedef struct BiTNode 
{ 
    char  data;
    struct BiTNode  *lchild;
	struct BiTNode  *rchild; 
                                     
} BiTree;

//-----------------------------------创建二叉树
BiTree *CreateBiTree(BiTree *T) 
{ 
char ch; 
if((ch=getchar())=='#') T=NULL; 
  else
  { 
      T=(BiTree *)malloc(sizeof(BiTNode )); 
      T->data=ch; 
      T->lchild = CreateBiTree(T->lchild); 
      T->rchild = CreateBiTree(T->rchild);
  } 
return T; 
} 



//------------------------------查找结点
/*Status searchBiTree(BiTree *T,TElemType x) 
{ 
	  BiTree *bt;
      if(T!=NULL) 
	  {
			if(bt->data==x)  
			printf("你查找的结点存在该二叉树中");
			return OK;
        	searchBiTree(T->lchild,x);         
			searchBiTree(T->rchild,x);    
        }
      else
		  printf("%d不在该树中",x);
		  return NULL;         
} 

*/
//------------------------------求深度
Status DepthBiTree (BiTree *T)
{ 
	int depthval,depthLeft,depthRight;
    if ( !T ) depthval = 0;
    else   
   {
     depthLeft = DepthBiTree( T->lchild );
     depthRight= DepthBiTree( T->rchild );
     depthval = 1 + (depthLeft > depthRight?depthLeft : depthRight);
   } 
   return depthval;
}

//----------------------------计算叶子结点数
Status countleaf(BiTree *T) 
{
    int num1;
	int num2;
	int num;     
    if (T==NULL) num=0;
    else
      if((T->lchild==NULL)&&(T->rchild==NULL)) num=1;
      else
	  {
		num1=countleaf (T->lchild);
		num2= countleaf(T->rchild);
		num= num1+num2;
	  }
return num;
}



// 先序遍历二叉树

void preorder(BiTree *T)
{
	if(T!=NULL)
	{
		printf("%2c",T->data); 
        preorder(T->lchild); 
        preorder(T->rchild);
	} 
} 


// 中序遍历二叉树

void Inorder(BiTree *T) 
{ 
struct BiTNode  *p; 
struct BiTNode  *stack[20]; 
int top=0; 

p=T; 
while(p||top!=0) 
{ 
while (p) 
{ 
stack[top++]=p; 
p=p->lchild ; 
} 
p=stack[--top]; 
printf("%c ",p->data ); 
p=p->rchild ; 
} 
} 


// 后序遍历二叉树
void Postorder (BiTree *T)
{  
   if (T!=NULL)
   {
      Postorder(T->lchild);  
      Postorder(T->rchild);
      printf("%2c",T->data);
   }
}


//------------------------交换左右孩子
void change_left_right(BiTree *T) 
{
	BiTree *temp;
	if (T) 
	{
       change_left_right(T->lchild);
       change_left_right(T->rchild);
       temp=T->lchild; 
	   T->lchild =T->rchild;
	   T->rchild=temp;
    }
}

int main()
{
	int i,j;
	BiTree *bt;
    printf("请按先序序列输入数据:\n"); 
    bt= NULL; 
    bt = CreateBiTree(bt); //and here 
    printf("先序遍历的结果为："); 
    preorder(bt); 
    printf("\n\n"); 
    printf("中序遍历的结果为："); 
    Inorder(bt); 
    printf("\n\n"); 
    printf("后序遍历的结果为：");    
	Postorder(bt); 
    printf("\n\n"); 
    printf("叶子结点总数目为:  n="); 
    i = countleaf(bt);
    printf("%d",i);
    printf("\n\n"); 
    printf("该二叉树的深度为:  h="); 
    j = DepthBiTree (bt);
    printf("%d",j);
    printf("\n\n"); 
	printf("交换左右孩子后结果如下:\n\n");
    change_left_right(bt);
    printf("先序遍历的结果为："); 
    preorder(bt); 
    printf("\n\n"); 
    printf("中序遍历的结果为："); 
    Inorder(bt); 
    printf("\n\n"); 
    printf("后序遍历的结果为：");    
	Postorder(bt); 
	printf("\n\n"); 
	printf("叶子结点总数目为:  n="); 
    i = countleaf(bt);
    printf("%d",i);
    printf("\n\n"); 
    printf("该二叉树的深度为:  h="); 
    j = DepthBiTree (bt);
    printf("%d",j);
    printf("\n\n"); 
return 0;
	 
}