二叉树算法应用.txt

数据结构二叉树算法的应用

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	char data;
	struct node *lchild,*rchild;
}NODE;

int count=0;

NODE *crt_bt_pre()
{  NODE *bt;
   char ch;
   scanf("%c",&ch);
   if(ch=='#') bt=NULL;
   else
   {  bt=(NODE *)malloc(sizeof(NODE));
      bt->data=ch;
	  bt->lchild=crt_bt_pre();
	  bt->rchild=crt_bt_pre();
   }
   return(bt);
}

void Countleaf(NODE *bt)
{ if(bt!=NULL)
{if((bt->lchild==NULL) && (bt->rchild==NULL))
{   count++;
     return;
}
Countleaf(bt->lchild);
Countleaf(bt->rchild);
}
}


int Countnode(NODE *bt)
{if(bt)
{count++;
 Countnode(bt->lchild);
 Countnode(bt->rchild);
return(count);
}}

int Treedepth(NODE *bt)
{  int ldep,rdep;
   if(bt==NULL)
	   return 0;
   else
   {  ldep=Treedepth(bt->lchild);
      rdep=Treedepth(bt->rchild);
	  if(ldep>rdep)
		  return ldep+1;
	  else
		  return rdep+1;
	  }
}


void main()
{ 
	NODE *bt;
	
	
	int x;

	
			printf("\n\t\t\t请输入按先序建立二叉树的结点序列：");
			printf("\n\t\t\t请输入根结点：");
			bt=crt_bt_pre();
			printf("\n\t\t\t二叉树建立成功!\n");
		
		
			Countleaf(bt);
			printf("\n\t\t\t该树有%d页结点\n",count);
		
		
			count=0;
			x=Countnode(bt);
			printf("\n\t\t\t该树有%d个结点\n",count);
		
		
		
			x=Treedepth(bt);
			printf("\n\t\t\t该树的深度为%d",x);
		

			
			printf("\t\t\t程序结束！\n");
		
		
	
}