112201.cpp

二叉树的创建以及利用递归进行前序遍历

// suju.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream.h>
#include <math.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

int n;
char ch;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode, *BiTree;
typedef struct{
	BiTree *base;		//栈底指针
	BiTree *top;		//栈顶指针
	int stacksize;	//栈的深度
	int length;		//当前元素个数
}SqStack;

int Visit(char e);
void CreateBiTree(BiTree &T);
int PreOrderTraverse(BiTree T, int(* Visit)(char e));
int InOrderTraverse(BiTree T, int(* Visit)(char e));
int PostOrderTraverse(BiTree T, int(* Visit)(char e));

int InitStack(SqStack &S);			//初始化栈
int Push(SqStack &S, BiTree e);		//入栈
int Pop(SqStack &S, BiTree &e);		//出栈
int GetTop(SqStack S, BiTree &e);

int main(int argc, char* argv[])
{
	BiTree T;
	cout << "请输入二叉树结点个数: ";
	cin >> n;
	cout << "请输入二叉树结点字符: " << endl;
	CreateBiTree(T);

	cout << "前序遍历" << endl;
	PreOrderTraverse(T, Visit);
	cout << endl;

	cout << "中序遍历" << endl;
	InOrderTraverse(T, Visit);
	cout << endl;

	cout << "后序遍历" << endl;
	PostOrderTraverse(T, Visit);
	cout << endl;

	return 0;
}
int Visit(char e)
{
	cout << e << ' ';
	return 1;
}
void CreateBiTree(BiTree &T)
{
	static int counter;
	if(counter < n)
	{
		counter++;
		cout << "第" << counter << "个结点: ";
		cin >> ch;
		if(ch == '0')
			T = NULL;
		else
		{
			if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))
				return;
			T->data = ch;
			CreateBiTree(T->lchild);
			CreateBiTree(T->rchild);
		}
	}
}
int PreOrderTraverse(BiTree T, int(* Visit)(char e))
{
	if(T)
	{
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild, Visit))
				if(PreOrderTraverse(T->rchild, Visit))
					return 1;
		return 0;
	}
	else
		return 1;
}
int InOrderTraverse(BiTree T, int(* Visit)(char e))
{
	SqStack S;
	BiTree p;
	InitStack(S);
	Push(S, T);
	while(S.length != 0)
	{
		while(GetTop(S, p) && p)
			Push(S, p->lchild);
		Pop(S, p);
		if(S.length != 0)
		{
			Pop(S, p);
			if(!Visit(p->data))
				return 0;
			Push(S, p->rchild);
		}
	}
	return 1;
}
int PostOrderTraverse(BiTree T, int(* Visit)(char e))
{
	if(T)
	{
		PostOrderTraverse(T->lchild, Visit);
		PostOrderTraverse(T->rchild, Visit);
		Visit(T->data);
	}
	return 1;
}


int InitStack(SqStack &S)
{
	S.base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));		//开辟空间
	if(!S.base)		//开辟空间不成功
		return 0;
	S.top = S.base;
	S.length = 0;
	S.stacksize = STACK_INIT_SIZE;
	return 1;
}
int Push(SqStack &S, BiTree e)//入栈
{
	if(S.top - S.base >= S.stacksize)//当前栈空间不足
	{
		S.base = (BiTree *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(BiTree));
		if(!S.base)
			return 0;
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;	//将元素压入栈中
	S.length++;
	return 1;
}
int Pop(SqStack &S, BiTree &e)	//出栈
{
	if(S.top == S.base) return 0; //空栈
	S.top--;
	S.length--;
	e = * S.top;
	return 1;
}
int GetTop(SqStack S, BiTree &e)
{
	if(S.top == S.base)
		return 0;
	e = *(S.top - 1);
	return 1;
}