数据结构[C语言]-二叉树前中后序-递归&非递归遍历代码集合

    由于二叉树非递归遍历实现时，需要用到栈和队列，因此，也将这部分代码这个头文件中了。

#include 
#include 





//定义数据元素类型
typedef char ElemType;

typedef struct BitNode{
	ElemType data;
	struct BitNode* lchild;//左孩子指针
	struct BitNode* rchild;//右孩子指针
}BitNode,BitTree;


typedef BitNode NodeType;

typedef struct TqStack{
	NodeType* data;//数据域
	struct TqStack* next;//指针域
}SNode,TqStack;


typedef struct TNode{
	NodeType* data;//数据域
	struct TNode* next;//指针域
}TNode;
typedef struct TqQueue{
	TNode* front;//队头
	TNode* rear;//队尾
}TqQueue;






int InitTqStack(TqStack** S){
	*S=(SNode*)malloc(sizeof(SNode));
	if (*S==NULL) return 0;
	(*S)->data=NULL;
	(*S)->next=NULL;
	return 1;
}


int IsEmptyTqStack(TqStack* S){
	return S->next==NULL?1:0;
}


NodeType* GetTopElemTqStack(TqStack* S){
	return S->next!=NULL?S->next->data:NULL;
}


int PushTqStack(TqStack** S,NodeType* e){
	SNode* p=*S;//辅助指针
	SNode* node=NULL;//新结点
	//查找尾结点
	//while (p->next!=NULL) p=p->next;
	//创建新结点
	node=(SNode*)malloc(sizeof(SNode));
	if (node==NULL) return 0;
	node->data=e;
	node->next=NULL;
	//printf("%dn",node);
	//插入结点
	node->next=p->next;
	p->next=node;
	return 1;
}


int PopTqStack(TqStack** S,NodeType** e){
	SNode* p=*S;
	SNode* delNode=NULL;
	if (p->next==NULL) return 0;
	//记录被删除结点
	delNode=p->next;
	*e=delNode->data;
	//删除结点
	p->next=delNode->next;
	free(delNode);
	return 1;
}





int InitTqQueue(TqQueue* Q){
	Q->front=Q->rear=(TNode*)malloc(sizeof(TNode));
	Q->front->next=NULL;
	Q->rear->next=NULL;
	return 1;
}


int IsEmptyTqQueue(TqQueue* Q){
	return Q->front==Q->rear?1:0;
}


int EnTqQueue(TqQueue* Q,NodeType* e){
	TNode* node=NULL;//新结点
	//创建新结点
	node=(TNode*)malloc(sizeof(TNode));
	if (node==NULL) return 0;
	node->data=e;
	node->next=NULL;
	//printf("%dn",node);
	//插入结点
	Q->rear->next=node;
	Q->rear=node;;
	return 1;
}


int DeTqQueue(TqQueue* Q,NodeType** e){
	TNode* delNode=NULL;
	if (IsEmptyTqQueue(Q)) return 0;
	delNode=Q->front->next;//记录被删除结点
	*e=delNode->data;
	//删除结点
	Q->front->next=delNode->next;
	if (Q->rear==delNode)
		Q->rear=Q->front;
	free(delNode);
	return 1;
}









int InitBitTree(BitTree** T,ElemType e){
	*T=(BitNode*)malloc(sizeof(BitNode));
	if (*T==NULL) return 0;
	(*T)->data=e;
	(*T)->lchild=NULL;
	(*T)->rchild=NULL;
	return 1;
}


int IsEmptyBitTree(BitTree* T){
	return T==NULL?1:0;
}


void visitBitNode(BitNode* node){
	if (node==NULL) return;
	printf("【 %d 】t",node->data);
}


void levelOrderBitTree(BitTree* T){
	TqQueue Q;
	InitTqQueue(&Q);
	//根节点入队
	EnTqQueue(&Q,T);
	while (IsEmptyTqQueue(&Q)!=1)
	{
		//队头元素出队
		DeTqQueue(&Q,&T);
		visitBitNode(T);//按层序顺序依次访问结点
		//判断左右子结点是否需要入队
		if (T->lchild!=NULL)
			EnTqQueue(&Q,T->lchild);
		if (T->rchild!=NULL)
			EnTqQueue(&Q,T->rchild);
	}
}



void preOrderBitTree(BitTree* T){
	if (T!=NULL)
	{
		preOrderBitTree(T->lchild);
		visitBitNode(T);
		preOrderBitTree(T->rchild);
	}
}


void inOrderBitTree(BitTree* T){
	if (T!=NULL)
	{
		visitBitNode(T);
		inOrderBitTree(T->lchild);
		inOrderBitTree(T->rchild);
	}
}


void postOrderBitTree(BitTree* T){
	if (T!=NULL)
	{
		postOrderBitTree(T->lchild);
		postOrderBitTree(T->rchild);
		visitBitNode(T);
	}
}


void preOrderBitTreeUnRecursion(BitTree* T){
	TqStack* S;
	InitTqStack(&S);
	//非递归遍历
	while (T!=NULL||IsEmptyTqStack(S)!=1)
	{
		if (T!=NULL)
		{
			visitBitNode(T);
			PushTqStack(&S,T);
			T=T->lchild;
		}else
		{
			PopTqStack(&S,&T);
			T=T->rchild;
		}
	}
	if (S!=NULL) free(S);
}


void inOrderBitTreeUnRecursion(BitTree* T){
	TqStack* S;
	InitTqStack(&S);
	while (T!=NULL||IsEmptyTqStack(S)!=1)
	{
		if (T!=NULL)
		{
			PushTqStack(&S,T);
			T=T->lchild;
		}
		else
		{
			PopTqStack(&S,&T);
			visitBitNode(T);
			T=T->rchild;
		}
	}
	if(S!=NULL){
		free(S);
	}
}


void postOrderBitTreeUnRecursion(BitTree* T){
	BitNode* pre=NULL;//记录最近一次访问过的结点
	TqStack *S;
	InitTqStack(&S);
	//非递归遍历
	while (T!=NULL||IsEmptyTqStack(S)!=1)
	{
		if (T!=NULL)
		{
			PushTqStack(&S,T);
			T=T->lchild;
		}else
		{
			T=GetTopElemTqStack(S);//获取栈顶结点
			if (T->rchild!=NULL&&T->rchild!=pre)
				T=T->rchild;
			else
			{
				PopTqStack(&S,&T);
				visitBitNode(T);
				pre=T;
				T=NULL;
			}
		}
	}
	//释放内存空间
	if (S!=NULL) free(S);
}




void printBitTreeInfo(BitTree* T){
	printf("Is Empty?%sn",(IsEmptyBitTree(T)?"Yes":"No"));
	printf("the left-son Tree is %x,the right-son Tree is %x.n",T->lchild,T->rchild);
	printf("preOrder sequence are as followings:n[");
	preOrderBitTree(T);
	printf("]n");
	printf("inOrder sequence are as followings:n[");
	inOrderBitTree(T);
	printf("]n");
	printf("postOrder sequence are as followings:n[");
	postOrderBitTree(T);
	printf("]n");
	printf("preOrder sequence with no-recursion are as followings:n[");
	preOrderBitTreeUnRecursion(T);
	printf("]n");
	printf("inOrder sequence with no-recursion are as followings:n[");
	inOrderBitTreeUnRecursion(T);
	printf("]n");
	printf("postOrder sequence with no-recursion are as followings:n[");
	postOrderBitTreeUnRecursion(T);
	printf("]n");
	printf("levelOrder sequence with no-recursion are as followings:n[");
	levelOrderBitTree(T);
	printf("]n");
}

    包含了部分链式栈和链式队列的测试代码，就还是保留着吧了。另外，树的结构可以按着tree_test()中的左右子树设置顺序画一下（T为根节点），就不贴图了。

#include "BitTree.h"


void tree_test(){
	BitTree* T;
	InitBitTree(&T,1);
	//创建结点
	BitNode* t_2=(BitNode*)malloc(sizeof(BitNode));
	t_2->data=2;
	t_2->lchild=NULL;t_2->rchild=NULL;
	BitNode* t_3=(BitNode*)malloc(sizeof(BitNode));
	t_3->data=3;
	t_3->lchild=NULL;t_3->rchild=NULL;
	BitNode* t_4=(BitNode*)malloc(sizeof(BitNode));
	t_4->data=4;
	t_4->lchild=NULL;t_4->rchild=NULL;
	BitNode* t_5=(BitNode*)malloc(sizeof(BitNode));
	t_5->data=5;
	t_5->lchild=NULL;t_5->rchild=NULL;
	BitNode* t_6=(BitNode*)malloc(sizeof(BitNode));
	t_6->data=6;
	t_6->lchild=NULL;t_6->rchild=NULL;

	//set tree ndoes
	T->lchild=t_2;
	T->rchild=t_3;
	t_2->rchild=t_4;
	t_4->lchild=t_6;
	t_3->rchild=t_5;

	//前序遍历

	printBitTreeInfo(T);


}

void stack_test(){
	TqStack* S;
	BitNode* t=(BitNode*)malloc(sizeof(BitNode));
	BitNode* t_2=(BitNode*)malloc(sizeof(BitNode));
	t_2->data=2;
	t_2->lchild=NULL;t_2->rchild=NULL;
	BitNode* t_3=(BitNode*)malloc(sizeof(BitNode));
	t_3->data=3;
	t_3->lchild=NULL;t_3->rchild=NULL;
	InitTqStack(&S);
	PushTqStack(&S,t_2);
	PushTqStack(&S,t_3);
	printf("is stack empty?%dn",IsEmptyTqStack(S));
	PopTqStack(&S,&t);
	printf("is stack empty?%dn",IsEmptyTqStack(S));
	//printf("%x,%x=%dn",S,S->next,S->next->data->data);
	printf("%dn",t->data);
	PopTqStack(&S,&t);
	printf("is stack empty?%dn",IsEmptyTqStack(S));
	//printf("%x,%x=%dn",S,S->next,S->next->data->data);
	printf("%dn",t->data);
}


void queue_test(){
	TqQueue Q;
	BitNode* t=(BitNode*)malloc(sizeof(BitNode));
	BitNode* t_2=(BitNode*)malloc(sizeof(BitNode));
	t_2->data=2;
	t_2->lchild=NULL;t_2->rchild=NULL;
	BitNode* t_3=(BitNode*)malloc(sizeof(BitNode));
	t_3->data=3;
	t_3->lchild=NULL;t_3->rchild=NULL;
	InitTqQueue(&Q);
	EnTqQueue(&Q,t_2);
	EnTqQueue(&Q,t_3);
	printf("is Empty?%dn",IsEmptyTqQueue(&Q));
	DeTqQueue(&Q,&t);
	printf("is Empty?%dn",IsEmptyTqQueue(&Q));
	printf("%dn",t->data);
	DeTqQueue(&Q,&t);
	printf("is Empty?%dn",IsEmptyTqQueue(&Q));
	printf("%dn",t->data);
	printf("front=%x,rear=%xn",Q.front,Q.rear);

}


int main(int argc,char** argv){
	tree_test();
	//stack_test();
	//queue_test();
	return 0;
}