crtree.cpp

先序遍历树

#include<math.h>
#include<stdio.h>
#include<malloc.h>
#define null 0
#define Stack_init_size 100

typedef struct treeNode{
	char data;
	struct treeNode *firstson,*nextsibling;
}Node,*trNode;

char *base;
int num_leaves=0;

int initStack(char *&top){
	
	top=(char *)malloc( Stack_init_size* sizeof(char));
	base=top;
	return 1;
}


int push(char *&top,char e){
		   	++top;
			*top=e;
		    return 1;
  }

  
char pop(char *&top){
	  --top;
	  return *top;
  }

 void	printfstack(char *to){
		 char e;
	      for(to;to>base;--to){
					e=*to;
					printf("%c",e);
				  }
	
	printf(" ");
  
  }
  
  int CreateBiTree(trNode &T){
    
    char ch;
	scanf("%c",&ch);
	if (ch=='#') T=null;
	else{ if(!(T=(Node *)malloc(sizeof(trNode )))) return 0;
	T->data=ch;
	CreateBiTree(T->firstson);
    CreateBiTree(T->nextsibling);
}
return 1;
}
 
  //先序遍历树
  void  inorder_see_all(trNode q){
	trNode p;
	p=q;
	while(p!=null){
		
			printf("%c ",p->data);
		
			if(p->firstson!=null)
             inorder_see_all(p->firstson);
			p=p->nextsibling;
		}
}
	//end inorder_see_all();
	
  
  
  
  void print_leaf_node(trNode q){

    trNode p;
	p=q;
	while(p!=null){
		
    if(p->firstson!=null)
			{
				
				
				
				print_leaf_node(p->firstson);
	}
			
			else {printf("%c ",p->data) ;  num_leaves++   ;}
		
			p=p->nextsibling;
		}
}//end inorder_see_all();

 
//求树的深度	
	
int depth(trNode tr){
	int depL,depr;
     if(tr==null) return 0;
	 else depL=depth(tr->firstson);
	      depr=depth(tr->nextsibling);
		    depL++;
		   if(depL>depr)return depL;
		    else
			return depr;
	 
 }//end depth();
	 
//输出叶子到根结点的路径	 
	 void outpath(trNode T,char *&top){
		trNode p;	
		p=T;
	
	    while(p!=null)
			{
				
		  push(top,p->data);
				
			
           if(p->firstson==null) {   
			printfstack(top);	
		   
		   
 }
				else
				
					
					outpath(p->firstson,top);
				    
				
				   
		           pop(top);
			     	p=p->nextsibling;
			}
	
	}//end outpath();

	

void main(){

	int dep;
		
     trNode m;

	CreateBiTree(m);
	printf("the inorder_see_all is: ");
	inorder_see_all(m);	
	
	printf("\n");
    

    
	char *i;
    initStack(i);
    
    printf("the outpath is: ");
	outpath(m,i);
	
	
	printf("\n");
	printf("the whole leaves  is: ");
	
	print_leaf_node(m);
	printf("\n");
	
	printf("The number of Leaves is: ");
	printf("%d\n",num_leaves);
	    
	printf("the depth is: ");
    dep=depth(m);
    printf("%d\n",dep);
	



}