(C语言)二叉树非递归遍历前序和中序(数据结构十四)

1.数据类型定义

在代码中为了清楚的表示一些错误和函数运行状态,我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义:

//定义数据结构中要用到的一些变量和类型
#ifndef HEAD_H
#define HEAD_H

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW   -2    //分配内存出错

typedef int  Status;     //函数返回值类型
typedef int  ElemType;   //用户定义的数据类型

#endif

2.遍历过程中用到的栈结构代码如下

LinearStack.h中

#ifndef LINEAR_STACK
#define LINEAR_STACK
#include "head.h"

#define  STACK_INIT_SIZE 100  
#define  STACK_INCREMENT 10    


typedef pBiNode Type;


typedef struct Stack{
	Type *base;   //栈底
	Type *top;    //栈顶
	int     size;    //栈大小
}Stack,*pStack;





//初始化栈
Status InitStack(pStack &S){
	S=(pStack)malloc(sizeof(Stack));
	Type* p=(Type*)malloc(STACK_INIT_SIZE*sizeof(Type));
	if(!p) return OVERFLOW;
	S->base=p;
	S->top=p;
	S->size=STACK_INIT_SIZE;
	return OK;
}

Status freeStack(pStack &S){
	free(S);
	S=NULL;
	return OK;
}
//销毁栈
Status DestroyStack(pStack &S){
	free(S->base);
	S->base=NULL;
	S->top=NULL;
	freeStack(S);
	return OK;
}
//清空栈
Status ClearStack(pStack &S){
	S->top=S->base;
	return OK;
}
//栈是否为空
Status StackEmpty(pStack S){
	return S->top==S->base;
}
//栈长度
int StackLength(pStack S){
	return S->top-S->base;
}
//得到栈顶数据级e
Status GetTop(pStack S,Type &e){
	e=*(S->top-1);
	return OK;
}
//入栈
Status Push(pStack &S,Type e){
	if(StackLength(S)>=S->size)
		S->base=(Type*)realloc(S->base,(S->size+STACK_INCREMENT)*sizeof(Type));
	if(!S->base) return OVERFLOW;
	S->top=S->base+StackLength(S);
	S->size+=STACK_INCREMENT;
	*S->top++=e;
	return OK;
}
//出栈
Status Pop(pStack &S,Type &e){
	if(StackLength(S)<1) return ERROR;
		e=*--S->top;
	return OK;
}

// Status print(Type e){
// 	printf("%d ",e);
// 	return OK;
// }

//用vistit遍历栈
Status StackTraverse(pStack S,Status(*visit)(Type)){
	while (S->top>S->base)
		(*visit)(*--S->top);
	return OK;
}
// Status printStack(pStack S){
// 	StackTraverse(S,print);
// 	return OK;
// }



#endif
3.二叉树结构代码如下
#ifndef BITREE_H
#define BITREE_H

#include "head.h"


typedef struct BiNode{
	ElemType data;
	struct BiNode *left,*right;
}BiNode,*pBiNode;


Status InsertRight(pBiNode &root,ElemType e);
Status InsertLeft(pBiNode &root,ElemType e);


Status InitBiTree(pBiNode &tree){
	tree=(pBiNode)malloc(sizeof(BiNode));
	if(!tree) return OVERFLOW;
	tree->data=-999999;
	tree->left=NULL;
	tree->right=NULL;
	return OK;
}
Status BiTreeEmpty(pBiNode root){
	if(root==NULL) return ERROR;
	return root->left==root->right && root->data==-999999;
}

Status HasNoNode(pBiNode root){
	if(root==NULL) return ERROR;
	return root->left==root->right ;
}

Status CreatTreeNode(pBiNode &node,ElemType e){
	node=(pBiNode)malloc(sizeof(BiNode));
	if(!node) return OVERFLOW;
	node->data=e;
	node->left=NULL;
	node->right=NULL;
	return OK;
}
Status InsertRight(pBiNode &root,ElemType e){
	if(root->right==NULL){
		if(e>root->data){
			pBiNode p;
			CreatTreeNode(p,e);
			root->right=p;
			return OK;
		}else{
			pBiNode p;
			CreatTreeNode(p,e);
			root->left=p;
			return OK;
		}

	}else{
		e>root->data? InsertRight(root->right,e):InsertLeft(root,e);
	}

}
Status InsertLeft(pBiNode &root,ElemType e){
	if(root->left==NULL){
		if(e>root->data){
			pBiNode p;
			CreatTreeNode(p,e);
			root->right=p;
			return OK;
		}else{
			pBiNode p;
			CreatTreeNode(p,e);
			root->left=p;
			return OK;
		}

	}else{
		e<=root->data?InsertLeft(root->left,e):InsertRight(root,e);
	}

}


Status InsertTree(pBiNode &root,ElemType e){
	if(BiTreeEmpty(root)){
		root->data=e;
		return true;
	}
	if(e>root->data){
		InsertRight(root,e);
	}else{
		InsertLeft(root,e);
	}
}


Status CreateBiTree(pBiNode &root,ElemType *a,int n){
	for (int i=0;i<n;i++)
	{
		InsertTree(root,a[i]);
	}
	return true;
}
 Status print(ElemType e ){
 	printf("%d ",e);
 	return true;
 }

Status PreOrderTraverse(pBiNode root,Status(*p)(int)){
	if(root){
		(*p)(root->data);
		PreOrderTraverse(root->left,p);
		PreOrderTraverse(root->right,p);
	}
	return OK;
}

Status MiddleOrderTraverse(pBiNode root,Status(*p)(int)){
	if(root){
		MiddleOrderTraverse(root->left,p);
		(*p)(root->data);
		MiddleOrderTraverse(root->right,p);
	}
	return OK;
}

Status AfterOrderTraverse(pBiNode root,Status(*p)(int)){
	if(root){
		AfterOrderTraverse(root->left,p);
		AfterOrderTraverse(root->right,p);
		(*p)(root->data);
	}
	return OK;
}

Status ClearBiTree(pBiNode &root){
	if(root){
		ClearBiTree(root->left);
		ClearBiTree(root->right);
		free(root);
		root==NULL;
	}
	return OK;
}


#endif

4.遍历测试如下

#include "BiTree.h"

#include "LinearStack.h"

//非递归中序
void MiddleTraverse(pBiNode Root){
	pStack S;
	InitStack(S);
	pBiNode p=Root;
	while(p||!StackEmpty(S)){
		if(p){
			Push(S,p);
			p=p->left;
		}else{
			Pop(S,p);
			printf("%d ",p->data);
			p=p->right;
		}
	}
}

//非递归前序
void PerTraverse(pBiNode Root){
	pStack S;
	InitStack(S);
	pBiNode p=Root;
	while(p||!StackEmpty(S)){
		if(p){
			printf("%d ",p->data);
			Push(S,p);
			p=p->left;
		}else{
			Pop(S,p);
			p=p->right;
		}
	}
}



void main(){
	ElemType a[14]={100,50,200,40,30,45,60,55,61,200,150,300,250,400};
	pBiNode root;
	InitBiTree(root);
	CreateBiTree(root,a,14);

	printf("前序:");
	PreOrderTraverse(root,print);

	printf("
中序:");
	MiddleOrderTraverse(root,print);

	printf("
后序:");
	AfterOrderTraverse(root,print);


	printf("
非递归前序:");
	PerTraverse(root);

	printf("
非递归中序:");
	MiddleTraverse(root);


	ClearBiTree(root);

}




5.插入的二叉树
6.遍历结果 

前序:100 50 40 30 45 60 55 61 200 150 300 250 400
中序:30 40 45 50 55 60 61 100 150 200 250 300 400
后序:30 45 40 55 61 60 50 150 250 400 300 200 100
非递归前序:100 50 40 30 45 60 55 61 200 150 300 250 400
非递归中序:30 40 45 50 55 60 61 100 150 200 250 300 400 




原文地址:https://www.cnblogs.com/whzhaochao/p/5023500.html