ツリーのいくつかの基本アルゴリズム

#include 
#include 

/** 
*	        
*	1.          （  、  、  、  ）
*	2.          （    ）
*	3.         
*	4.         
*	5.        
*
*/

typedef struct BTNode{
	int data;
	struct BTNode * lchild;
	struct BTNode * rchild;
}BTNode;

/**
*	          
*	1.  、  、  、  
*/
//  
void Trave1(BTNode * root){
	if(root != NULL){
		printf("%d",root->data);
		Trave1(root ->lchild);
		Trave1(root ->rchild);
	}
}

//  
void Trave2(BTNode * root){
	if(root != NULL){
		Trave2(root ->lchild);
		printf("%d",root->data);
		Trave2(root -> rchild);
	}
}

//  
void Trave3(BTNode * root){
	if(root != NULL){
		Trave3(root->lchild);
		Trave3(root->rchild);
		printf("%d",root->data);
	}
}

#define maxSize 100
//         
void Trave4(BTNode * root){
	//            ,           	
	BTNode * que[maxSize];
	int front = 0,rear = 0;
	if(root != NULL){
		//     
		rear = (rear + 1)%maxSize;
		que[rear] = root;
		while(front != rear){//       
			//  
			front = (front +1)%maxSize;
			printf("%d",que[front]->data);
			//      
			if(que[front]->lchild != NULL){
				rear = (rear + 1)%maxSize;
				que[rear] = que[front]->lchild;
			}
			if(que[front]->rchild != NULL){
				rear = (rear + 1)%maxSize;
				que[rear] = que[front]->rchild;
			}
		}
	}	
}

/**
*	        ，  '-1'    
*	  :          ，       ，        
*/
BTNode * createTree(){
	printf("                 
");
	int data;
	scanf("%d",&data);
	if(data == -1){
		return NULL;
	}else{
		BTNode * root = (BTNode *)malloc(sizeof(BTNode));
		root->data = data;
		root -> lchild = createTree();
		root -> rchild = createTree();
		return root;
	}
}

/**
*	         
*	  :              ，    +1     ，         
*/
int getDepth(BTNode * root){
	int ldepth,rdepth;
	if(root == NULL){
		return 0;
	}else{
		ldepth = getDepth(root->lchild);
		rdepth = getDepth(root->rchild);
		return (ldepth>rdepth?ldepth:rdepth) + 1;
	}
}

/**
*	         
*	  :     ，           ，             
*		     ，              ，                   
*		                 ，                 
*/
typedef struct{
	BTNode * node;
	int flag;	//   1   n
}ST;

int getWidth(BTNode * root){
	//         
	ST * que[maxSize];
	int front=0,rear=0;
	int flag = 1;
	if(root != NULL){
		//     ,    1，   1 
		ST * p = (ST *)malloc(sizeof(ST));
		p->flag = flag;
		p->node = root;
		rear ++;	
		que[rear] = p;	
		BTNode * q;
		while(root != NULL){
			front ++;	//    ，            
			q = que[front]->node;
			if(que[front]->flag > flag){	//        ，  flag    ,     flag = que[front]->flag   
				flag ++;	
			}
			if(que[front]->node->lchild != NULL){	//     ，      
				rear ++;
				/*
				que[rear]->node = q->lchild;
				que[rear]->flag = flag + 1;
				*/
				p = (ST *)malloc(sizeof(ST));
				p->node = q->lchild;
				p->flag = flag + 1;
				que[rear] = p;
			}
			if(que[front]->node->rchild != NULL){
				rear ++;
				/*
				que[rear]->node = q->rchild;
				que[rear]->flag = flag + 1;
				*/
				p = (ST *)malloc(sizeof(ST));
				p->node = q->rchild;
				p->flag = flag + 1;
				que[rear] = p;
			}
		}
		//           
		int i,j,max=0;
		for(i=1;i<=flag;i++){
			int n=0;
			for(j=1;j<=rear;j++){
				if(que[j]->flag == i){
					n++;
				}
			}
			if(max<n){
				max = n;
			}
		}
		return max;
	}
	return 0;
}
//       
int getWidth2(BTNode * root){
	ST que[maxSize];
	int flag = 1;
	int front=0,rear=0;
	if(root !=NULL){
		rear ++;
		que[rear].node = root;
		que[rear].flag = flag;
		BTNode * q;
		while(front != rear){
			front ++;
			q = que[front].node;
			flag = que[front].flag;
			if(q->lchild != NULL){
				rear ++;
				que[rear].node = q;
				que[flag].flag = flag + 1;
			}
			if(q->rchild != NULL){
				rear ++;
				que[rear].node = q;
				que[flag].flag = flag + 1;
			}
		}
		int max,n,i,j;
		for(i=1;i<=flag;i++){
			n = 0;
			for(j=1;j<=flag;j++){		
				if(que[j].flag == i){
					n++;
				}
			}
			if(max<n){
				max = n;
			}
		}
		return max;
	}
	return 0;
}

/**
*	            
*	  :             ，         
*/
void traveByStack(BTNode * root){
	BTNode * stack[maxSize];
	BTNode * p;
	int top = -1;
	if(root != NULL){
		//     
		stack[top] = root;
		while(top != -1){	//      
			//  
			p = stack[top--];
			printf("%d",p->data);
			if(p->rchild!=NULL){//     ，      
				stack[++top] = p->rchild;
			}
			if(p->lchild!=NULL){//     ，      ，                        
				stack[++top] = p->lchild;
			}
		}
	}
}

/**
*	            
*	  :              ，        ，            ，             
*		    ，        ，           ，      ，     ，       
*		  ，   ，  ，    ，               ，             p    ，  ，  
*		      ，        ，      ，              
*/
void traveByStack2(BTNode * root){
	BTNode * stack[maxSize];
	int top = -1;
	BTNode * p = root;
	//     
	if(root != NULL){
		while(top!=-1||p!=NULL){	//    ||p!=null       p       ，              ，     
			while(p!= NULL){//        ，          
				stack[++top] = p;
				p=p->lchild;
			}
			//         ，             
			if(top != -1){
				printf("%d",stack[top]->data);
				p = stack[top--]->rchild;
			}
		}	
	}
}

int main(){
	printf("    
");
	BTNode * p;
	p = createTree();
	int width = getWidth2(p);
	printf("%d",width);
	return 0;
}