二叉树的遍历方法（C语言）

前言：二叉树是一种基础的数据模型，学会遍历二叉树可以帮助我们解决很多问题，所以今天和大家讨论的是有关二叉树如何遍历的问题。

题目要求：完成二叉树的先序遍历，中序遍历，后序遍历的递归，非递归遍历，以及层次遍历，并计算树的高度。（从文件中读取，并以文件的形式输出）

二叉树示例（“#”代表空树）

 1.准备工作

#include
#include
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;                //BiTNode为结构体变量   BiTree为结构体指针

2.创建二叉树

BiTree CreateTree(FILE*fp_1) {
    BiTree T;
    char ch, trmp;
    fscanf(fp_1,"%c",&ch);
    if(ch=='#')
        T=NULL;
    else {
        T=(BiTNode*)malloc(sizeof(BiTNode));
        T->data=ch;
        T->lchild=CreateTree(fp_1);
        T->rchild=CreateTree(fp_1);
    }
    return T;
}

3.前序遍历（递归）

void PreOrderTraverse(BiTree T) {
	if(T) {
		FILE*fp;
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",T->data);
		fclose(fp);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

4.前序遍历（非递归）

void PreOrderTraverse_1(BiTree T) {
	FILE*fp;
	BiTree stack[100],node;
	int top=0;
	if(T==NULL) {
		printf("tree is empty--n");
		return ;
	} else {
		top++;
		stack[top]=T;
		while(top>0) {
			node=stack[top--];
			fp=fopen("test_1.txt","a");
			fprintf(fp,"%c ",node->data);
			fclose(fp);
			if(node->rchild!=NULL)
				stack[++top]=node->rchild;
			if(node->lchild!=NULL)
				stack[++top]=node->lchild;
		}
	}
}

5.中序遍历（递归）

void InOrderTraverse(BiTree T) {
	if(T) {
		FILE*fp;
		InOrderTraverse(T->lchild);
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",T->data);
		fclose(fp);
		InOrderTraverse(T->rchild);
		
	}
}

6.中序遍历（非递归）

void InOrderTraverse_1(BiTree T) {
	BiTree stack[100],node;
	int top=0;
	FILE*fp;
	if(T==NULL) {
		printf("tree is empty--n");
		return ;
	}
	node=T;
	while(node!=NULL||top>0) {
		while(node!=NULL) {
			stack[++top]=node;
			node=node->lchild;
		}
		node=stack[top--];					//出栈 
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",node->data);
		fclose(fp);
		node=node->rchild;
	}
}

7.后序遍历（递归）

void PostOrderTraverse(BiTree T) {
	if(T) {
		FILE*fp;
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",T->data);
		fclose(fp);
	}
}

8.后序遍历（非递归）

void PostOrderTraverse_1(BiTree T) {
	BiTree p=T,stack[100],have_visited=NULL;
	int num=0;
	FILE*fp;
	while(p!=NULL||num>0){
		while(p!=NULL){
			stack[num++]=p;
			p=p->lchild;
		}
		p=stack[num-1];
		if(p->rchild==NULL||p->rchild==have_visited){	//要么右子树为空，要么右子树已经被访问 
			fp=fopen("test_1.txt","a");
			fprintf(fp,"%c ",p->data);
			fclose(fp);
			num--;
			have_visited=p;
			p=NULL; 
		}
		else
		p=p->rchild;
	}
}

9.层次遍历 

void level(BiTree T) {
	FILE*fp;
	BiTree queue[20],pTemp;
	int cur=0,pre=0;						//队列中cur是队尾，pre是队头 
	queue[cur++]=T;
	while(cur!=pre) {
		pTemp=queue[pre++];					//出队列 
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",pTemp->data);
		fclose(fp);
		if(pTemp->lchild!=NULL)
			queue[cur++]=pTemp->lchild;		//入队列 
		if(pTemp->rchild!=NULL)
			queue[cur++]=pTemp->rchild;		//入队列 
	}	
}

10.树的高度

int height(BiTree T) {						//树的高度
	int ld,rd;
	if(T==NULL)
		return 0;
	else {
		ld=height(T->lchild);
		rd=height(T->rchild);
		return 1+(ld>rd?ld:rd);
	}
}

总代码

#include
#include
typedef struct BiTNode {
	char data;
	struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;				//BiTNode为结构体变量   BiTree为结构体指针

BiTree CreateTree(FILE*fp_1) {
	BiTree T;
	char ch, trmp;
	fscanf(fp_1,"%c",&ch);
	if(ch=='#')
		T=NULL;
	else {
		T=(BiTNode*)malloc(sizeof(BiTNode));
		T->data=ch;
		T->lchild=CreateTree(fp_1);
		T->rchild=CreateTree(fp_1);
	}
	return T;
}

void InOrderTraverse(BiTree T) {
	if(T) {
		FILE*fp;
		InOrderTraverse(T->lchild);
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",T->data);
		fclose(fp);
		InOrderTraverse(T->rchild);
		
	}
}

void PreOrderTraverse(BiTree T) {
	if(T) {
		FILE*fp;
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",T->data);
		fclose(fp);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

void PostOrderTraverse(BiTree T) {
	if(T) {
		FILE*fp;
		
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",T->data);
		fclose(fp);
	}
}

void InOrderTraverse_1(BiTree T) {
	BiTree stack[100],node;
	int top=0;
	FILE*fp;
	if(T==NULL) {
		printf("tree is empty--n");
		return ;
	}
	node=T;
	while(node!=NULL||top>0) {
		while(node!=NULL) {
			stack[++top]=node;
			node=node->lchild;
		}
		node=stack[top--];					//出栈 
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",node->data);
		fclose(fp);
		node=node->rchild;
	}
}

void PreOrderTraverse_1(BiTree T) {
	FILE*fp;
	BiTree stack[100],node;
	int top=0;
	if(T==NULL) {
		printf("tree is empty--n");
		return ;
	} else {
		top++;
		stack[top]=T;
		while(top>0) {
			node=stack[top--];
			fp=fopen("test_1.txt","a");
			fprintf(fp,"%c ",node->data);
			fclose(fp);
			if(node->rchild!=NULL)
				stack[++top]=node->rchild;
			if(node->lchild!=NULL)
				stack[++top]=node->lchild;
		}
	}
}

void PostOrderTraverse_1(BiTree T) {
	BiTree p=T,stack[100],have_visited=NULL;
	int num=0;
	FILE*fp;
	while(p!=NULL||num>0){
		while(p!=NULL){
			stack[num++]=p;
			p=p->lchild;
		}
		p=stack[num-1];
		if(p->rchild==NULL||p->rchild==have_visited){	//要么右子树为空，要么右子树已经被访问 
			fp=fopen("test_1.txt","a");
			fprintf(fp,"%c ",p->data);
			fclose(fp);
			num--;
			have_visited=p;
			p=NULL; 
		}
		else
		p=p->rchild;
	}
}

void level(BiTree T) {
	FILE*fp;
	BiTree queue[20],pTemp;
	int cur=0,pre=0;						//队列中cur是队尾，pre是队头 
	queue[cur++]=T;
	while(cur!=pre) {
		pTemp=queue[pre++];					//出队列 
		fp=fopen("test_1.txt","a");
		fprintf(fp,"%c ",pTemp->data);
		fclose(fp);
		if(pTemp->lchild!=NULL)
			queue[cur++]=pTemp->lchild;		//入队列 
		if(pTemp->rchild!=NULL)
			queue[cur++]=pTemp->rchild;		//入队列 
	}	
}

int height(BiTree T) {						//树的高度
	int ld,rd;
	if(T==NULL)
		return 0;
	else {
		ld=height(T->lchild);
		rd=height(T->rchild);
		return 1+(ld>rd?ld:rd);
	}
}

int main() {
	BiTree T;
	FILE*fp_1;
	fp_1=fopen("test_2.txt","r");
	T=CreateTree(fp_1);
	fclose(fp_1);
	FILE*fp;
	fp=fopen("test_1.txt","w");
	fprintf(fp,"先序遍历：");
	fclose(fp);
	PreOrderTraverse(T);
	fp=fopen("test_1.txt","a");
	fprintf(fp,"n");
	fclose(fp);
	
	fp=fopen("test_1.txt","a");
	fprintf(fp,"中序遍历：");
	fclose(fp);
	InOrderTraverse(T);
	fp=fopen("test_1.txt","a");
	fprintf(fp,"n");
	fclose(fp);
	
	fp=fopen("test_1.txt","a");
	fprintf(fp,"后序遍历：");
	fclose(fp);
	PostOrderTraverse(T);
	fp=fopen("test_1.txt","a");
	fprintf(fp,"n");
	fclose(fp);
	
	fp=fopen("test_1.txt","a");
	fprintf(fp,"非递归先序遍历：");
	fclose(fp);
	PreOrderTraverse_1(T);
	fp=fopen("test_1.txt","a");
	fprintf(fp,"n");
	fclose(fp);

	fp=fopen("test_1.txt","a");
	fprintf(fp,"非递归中序遍历：");
	fclose(fp);
	InOrderTraverse_1(T);
	fp=fopen("test_1.txt","a");
	fprintf(fp,"n");
	fclose(fp);

	fp=fopen("test_1.txt","a");
	fprintf(fp,"非递归后序遍历：");
	fclose(fp);
	PostOrderTraverse_1(T);
	fp=fopen("test_1.txt","a");
	fprintf(fp,"n");
	fclose(fp);
	
	fp=fopen("test_1.txt","a");
	fprintf(fp,"层次遍历：");
	fclose(fp);
	level(T);
	fp=fopen("test_1.txt","a");
	fprintf(fp,"n二叉树的高度为：%dn",height(T));
	fclose(fp);
	return 0;
}

输入样例

 输出样例