树和二叉树---C语言利用栈实现二叉树的递归、非递归的前、中、后序遍历

时间：2022-03-24 19:38:17

C语言利用栈实现二叉树的递归、非递归的前、中、后序遍历。

以下代码分为三部分：1、Define.h头文件，基本声明        2、SqStack.h头文件，栈的基本声明和操作     3、树的基本声明和操作, 以及遍历的实现

1、Define.h头文件，基本声明


Defiine.h
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX 10

typedef char SElemType;
typedef char TElemType;
typedef int Status;

typedef struct BiTNode
{
	TElemType data;
	int flag;
	struct BiTNode *lchild, *rchild;		//左右孩子指针
}BiTNode, *BiTree;

2、SqStack.h头文件，栈的基本声明和操作 


SqStack.h
#include<stdio.h>
#include<stdlib.h>
#include"Define.h"
#include<string.h>



typedef struct
{
	BiTree *base;
	BiTree *top;
	int stacksize;
}SqStack;

Status InitStack(SqStack *S)					//构造一个空栈
{
	S->base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTNode));
	if (!S->base)
	{
		exit(OVERFLOW);
	}
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
//	printf("初始化成功!\n");

	return OK;
}

Status GetTop(SqStack S, BiTree *e)			//用e返回栈顶的元素
{
	if (S.top == S.base)
	{
		return ERROR;
	}
	(*e) = *(--S.top);

	return OK;
}

Status Push(SqStack *S, BiTree e)			//插入元素e为新的栈顶元素
{
	if (S->top - S->base >= S->stacksize)
	{
		S->base = (BiTree *)realloc(S->base, 
			(S->stacksize + STACKINCREMENT) * sizeof(BiTNode));
		if (! S->base)
		{
			exit(OVERFLOW);
		}
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top ++ = e;

	return OK;
}
Status Pop(SqStack *S, BiTree *e)
{
	if (S->top == S->base)
	{
		return ERROR;
	}
	else
	{
		*e = * --S->top;
	}

	return OK;
}

Status DestroyStack(SqStack *S)					//销毁栈
{
	if (S->top == S->base)
	{
		return ERROR;
	}
	S->top = S->base;
	return OK;
}

Status StackEmpty(SqStack S)
{
	if (S.top == S.base)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
3、树的基本声明和操作, 以及遍历的实现 


#include "SqStack.h"




Status CreateBiTree(BiTree *T);				//先序建立二叉树
Status PrintElement(TElemType e);			//输入元素
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e));			//先序遍历二叉树的递归算法
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e));			//中序遍历二叉树的递归算法
Status PostOrderTraverse(BiTree T, Status (* Visit)(TElemType e));			//后序遍历二叉树的递归算法

Status PreOrderTraverseNo1(BiTree T, Status (* Visit)(TElemType e));		//前续遍历二叉树的非递归算法1
Status InOrderTraverseNo1(BiTree T, Status (* Visit)(TElemType e));			//中续遍历二叉树的非递归算法1
Status PostOrderTraverseNo1(BiTree T, Status (* Visit)(TElemType e));		//后续遍历二叉树的非递归算法1

Status PreOrderTraverseNo2(BiTree T, Status (* Visit)(TElemType e));		//前续遍历二叉树的非递归算法2(优化)
Status InOrderTraverseNo2(BiTree T, Status (* Visit)(TElemType e));			//中续遍历二叉树的非递归算法2(优化)
Status PostOrderTraverseNo2(BiTree T, Status (* Visit)(TElemType e));		//后续遍历二叉树的非递归算法2(优化)

Status CreateBiTree(BiTree *T)
{
	char ch;
	ch = getchar();
	if (ch == ' ')
	{
		(*T) = NULL;
	}
	else
	{
		if (!((*T) = (BiTNode *)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		(*T)->data = ch;
		(*T)->flag = 0;
		CreateBiTree(&((*T)->lchild));
		CreateBiTree(&((*T)->rchild));
	}

	return OK;
}

Status PrintElement(TElemType e)
{
	printf("%c ", e);
	return OK;
}

Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e))				//先序遍历二叉树的递归算法
{
	if (T)
	{
		if (Visit(T->data))
		{
			if (PreOrderTraverse(T->lchild, Visit))
			{
				if (PreOrderTraverse(T->rchild, Visit))
				{
					return OK;
				}
			}
		}
		return ERROR;
	}
	else 
	{
		return OK;
	}
}

Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e))			//中序遍历二叉树的递归算法
{
	if (T)
	{
		if (InOrderTraverse(T->lchild, Visit))
		{
			if (Visit(T->data))
			{
				if (InOrderTraverse(T->rchild, Visit))
				{
					return OK;
				}
			}
		}
		return ERROR;
	}
	else 
	{
		return OK;
	}
}

Status PostOrderTraverse(BiTree T, Status (* Visit)(TElemType e))		//后序遍历二叉树的递归算法
{	
	if (T)
	{
		if (PostOrderTraverse(T->lchild, Visit))
		{
			if (PostOrderTraverse(T->rchild, Visit))
			{
				if (Visit(T->data))
				{
					return OK;
				}
			}
		}
		return ERROR;
	}
	else 
	{
		return OK;
	}
}

Status PreOrderTraverseNo1(BiTree T, Status (* Visit)(TElemType e))		//前续遍历二叉树的非递归算法1
{
	SqStack S;
	BiTree p;
	InitStack(&S);
	Push (&S, T);
	while (!StackEmpty(S))
	{
		while (GetTop(S, &p) && p)
		{
			if (!Visit(p->data))
			{
				return ERROR;
			}
			Push(&S, p->lchild);
		}
		Pop (&S, &p);
		if (!StackEmpty(S))
		{
			Pop(&S, &p);
			Push (&S, p->rchild);
		}
	}
	return OK;
}

Status InOrderTraverseNo1(BiTree T, Status (* Visit)(TElemType e))			//中续遍历二叉树的非递归算法1
{
	SqStack S;
	BiTree p;
	InitStack(&S);
	Push (&S, T);
	while (!StackEmpty(S))
	{
		while (GetTop(S, &p) && p)
		{
			Push(&S, p->lchild);
		}
		Pop (&S, &p);
		if (!StackEmpty(S))
		{
			Pop(&S, &p);
			if (!Visit(p->data))
			{
				return ERROR;
			}
			Push (&S, p->rchild);
		}
	}
	return OK;
}

Status PostOrderTraverseNo1(BiTree T, Status (* Visit)(TElemType e))		//后续遍历二叉树的非递归算法1
{
	SqStack S;
	BiTree p;
	InitStack(&S);
	Push (&S, T);
	while (!StackEmpty(S))
	{
		while (GetTop(S, &p) && p)
		{
			if (p->flag == 0)
			{
				p->flag ++;
				Push(&S, p->lchild);
			}
			else if (p->flag == 1)
			{
				p->flag ++;
				Push(&S, p->rchild);
			}
			else
			{
				Pop(&S, &p);
				p->flag = 0;
				Visit(p->data);
			}
		}
		Pop(&S, &p);
		if (!StackEmpty(S))
		{
			GetTop(S, &p);
			if (p->flag == 1)
			{	
				p->flag ++;
				Push(&S, p->rchild);
			}
			else if (p->flag == 2)
			{
				Pop(&S, &p);
				p->flag = 0;
				Visit(p->data);
			}
		}
	}

	return 0;
}

Status PreOrderTraverseNo2(BiTree T, Status (* Visit)(TElemType e))			//前续遍历二叉树的非递归算法2(优化)
{
	{
	SqStack S;
	BiTree p;
	InitStack(&S);
	p = T;
	while (p || !StackEmpty(S))
	{
		if (p)
		{
			Push(&S, p);
			if (!Visit(p->data))
			{
				return ERROR;
			}
			p = p->lchild;
		}
		else
		{
			Pop(&S, &p);
			p = p->rchild;
		}
	}
	return OK;
}
}

Status InOrderTraverseNo2(BiTree T, Status (* Visit)(TElemType e))			//中续遍历二叉树的非递归算法2(优化)
{
	SqStack S;
	BiTree p;
	InitStack(&S);
	p = T;
	while (p || !StackEmpty(S))
	{
		if (p)
		{
			Push(&S, p);
			p = p->lchild;
		}
		else
		{
			Pop(&S, &p);
			if (!Visit(p->data))
			{
				return ERROR;
			}
			p = p->rchild;
		}
	}
	return OK;
}

Status PostOrderTraverseNo2(BiTree T, Status (* Visit)(TElemType e))		//后续遍历二叉树的非递归算法2(优化)
{
	SqStack S;
	BiTree p;
	InitStack(&S);
	p = T;
	while (p || !StackEmpty(S))
	{
		if (p->flag == 0)
		{
			p->flag ++;
			Push(&S, p);
			p = p->lchild;
		}
		else if (p->flag == 1)
		{
			p->flag ++;
			p = p->rchild;
		}
		else if (p->flag == 2)
		{
			Pop(&S, &p);
			Visit(p->data);
			if (StackEmpty(S))
			{
				break;
			}
			GetTop(S, &p);
		}
		if (!p)
		{
			GetTop(S, &p);
		}
	}

	return 0;
}

int main()
{
	BiTree T;
	printf("先序建立二叉树, 请输入元素：\n");
	CreateBiTree(&T);
	printf("递归先序遍历二叉树：\n");
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	printf("递归中序遍历二叉树：\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	printf("递归后序遍历二叉树：\n");
	PostOrderTraverse(T, PrintElement);
	printf("\n");
	printf("非递归先序遍历二叉树（算法1）：\n");
	PreOrderTraverseNo1(T, PrintElement);
	printf("\n");
	printf("非递归中序遍历二叉树（算法1）：\n");
	InOrderTraverseNo1(T, PrintElement);
	printf("\n");
	printf("非递归后序遍历二叉树（算法1）：\n");
	PostOrderTraverseNo1(T, PrintElement);
	printf("\n");

	printf("非递归先序遍历二叉树（算法2,优化）：\n");
	PreOrderTraverseNo2(T, PrintElement);
	printf("\n");
	printf("非递归中序遍历二叉树（算法2,优化）：\n");
	InOrderTraverseNo2(T, PrintElement);
	printf("\n");
	printf("非递归后序遍历二叉树（算法2,优化）：\n");
	PostOrderTraverseNo2(T, PrintElement);
	printf("\n");

	return 0;
}



标签：

相关文章