数据结构实验五之二叉树相关操作

今天复习，突然发现漏了个函数没有写进来，顺便加了个层序遍历。

OK,我们先把头文件拽过来

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std; 
#define MAX_SIZE 1024
typedef char TElemType;
typedef char SeqTree[MAX_SIZE];//顺序二叉树的定义
typedef struct BiNode {//链式二叉树的定义
	TElemType data;
	struct BiNode* lchild, *rchild;
}*Bitree, BiTnode;
#define STACK_INIT_SIZE 100
#define STACKINCREASEMENT 10
#define OK 1

typedef struct {//栈的定义
	Bitree* base;
	Bitree* top;
	int stacksize;
}SqStack;

接下来是函数体，有点长的亚子。

void CreatSeqTree(SeqTree tree, int i)
{
	char ch;
	cin >> ch;
	if (ch == 'N') {
		//tree[i] = '\0';
		return;
	}
	tree[i] = ch;

	CreatSeqTree(tree, 2 * i);
	CreatSeqTree(tree, 2 * i + 1);
}
void InitSeqTree(SeqTree &tree) {
	memset(tree, 0, MAX_SIZE);
}



SqStack InitStack(SqStack& S) {
	S.base = (Bitree*)malloc(sizeof(Bitree) * STACK_INIT_SIZE);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return S;
}

Bitree GetTop(SqStack S, Bitree &e) {
	if (S.top == S.base) {
		cout << "遍历结束";
		exit(OVERFLOW);
	}
	e = *(S.top - 1);
	return e;
}

bool Push(SqStack& S, Bitree &e) {
	if (S.top - S.base >= S.stacksize) {
		S.base = (Bitree*)realloc(S.base, (S.stacksize + STACKINCREASEMENT) * sizeof(Bitree));
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREASEMENT;
	}
	*S.top++ = e;
	return 1;
}
Bitree Pop(SqStack &S, Bitree &e) {
	if (S.top == S.base) return 0;
	e = *--S.top;
	return e;
}

void CreateBitree(Bitree &T) {

	char c;
	cin >> c;
	if (c == 'N') T = NULL;
	else {
		if (!(T = (BiNode*)malloc(sizeof(BiNode)))) exit(OVERFLOW);
		T->data = c;
		CreateBitree(T->lchild);
		CreateBitree(T->rchild);
	}
}

bool PreOrder_print(Bitree T) {
	//前序遍历输出
	if (T) {
		cout << T->data << " ";
		if (PreOrder_print(T->lchild))
			if (PreOrder_print(T->rchild))
				return true;
		return false;
	}
	else
		return true;
}

void InOrder_print(Bitree T, SqStack S) {//算法1
	Bitree P = T;
	Push(S, P);
	while (!(S.top - S.base == 0)) {
		while (GetTop(S, P) && P) Push(S, P->lchild);
		Pop(S, P);
		if (!(S.top - S.base == 0)) {
			Pop(S, P);
			cout << P->data << " ";
			Push(S, P->rchild);
		}

	}


}

void LevelorderTraversal(Bitree BT) {
	if (BT == NULL)
		return;
	Bitree queue[100];
	Bitree q;
	int tail = 0, head = 0;
	if (BT) {
		queue[tail++] = BT;
		while (head != tail) {
			q = queue[head++];
			printf("%c ", q->data);
			if (q->lchild) queue[tail++] = q->lchild;
			if (q->rchild) queue[tail++] = q->rchild;
		}

	}
}

void InOrder_print2(Bitree T, SqStack S) {//算法2
	Bitree P = T;
	while (P || !(S.top - S.base == 0))
	{
		if (P) { Push(S, P); P = P->lchild; }
		else {
			Pop(S, P);
			cout << P->data << " ";
			P = P->rchild;
		}
	}
}

void InOrderTravel(Bitree T)
{//常规中续遍历
	if (T == NULL)
		return;
	InOrderTravel(T->lchild);
	printf("%c ", T->data);
	InOrderTravel(T->rchild);

}

void TailOrderTravel(Bitree T)
{//常规后续遍历
	if (T == NULL)
		return;
	TailOrderTravel(T->lchild);
	TailOrderTravel(T->rchild);
	printf("%c ", T->data);
}

void preOrder(char *BT, int i) //先序遍历(递归法)
{
	if (BT[i] != 0)
	{
		printf("%c ", BT[i]);
		preOrder(BT, 2 * i);
		preOrder(BT, 2 * i + 1);
	}
}

最后，主函数

int main() {
	Bitree T, T4, T5,T6;
	SqStack S;

	cout << "-------层序遍历二叉树-------" << endl;
	cout << "先序输入二叉树（空用N表示）" << endl;
	CreateBitree(T6);
	LevelorderTraversal(T6);
	cout << endl;
	cout << "-------前序遍历二叉树-------" << endl;
	cout << "先序输入二叉树（空用N表示）" << endl;
	CreateBitree(T);
	PreOrder_print(T);
	cout << endl;
	cout << "-------中序遍历二叉树-------" << endl;
	cout << "先序输入二叉树（空用N表示）" << endl;
	CreateBitree(T4);
	InOrderTravel(T4);
	cout << endl;

	cout << "-------后序遍历二叉树-------" << endl;
	cout << "先序输入二叉树（空用N表示）" << endl;
	CreateBitree(T5);
	TailOrderTravel(T5);
	cout << endl;
	Bitree T2;
	cout << "-------栈的方式(算法1）中序遍历二叉树-------" << endl;
	cout << "先序输入二叉树（空用N表示）" << endl;
	CreateBitree(T2);
	InitStack(S);
	InOrder_print(T2, S);
	cout << endl;
	cout << "-------栈的方式(算法2）中序遍历二叉树-------" << endl;
	cout << "先序输入二叉树（空用N表示）" << endl;
	Bitree T3;
	SqStack S3;
	InitStack(S3);
	CreateBitree(T3);
	InOrder_print2(T3, S3);
	cout << endl;
	cout << "----------------------------以下是顺序二叉树--------------------------" << endl;
	SeqTree tree ;
	InitSeqTree(tree);
	printf("请先序输入二叉树：\n");
	CreatSeqTree(tree, 1);
	cout << "先序遍历结果为：";
	preOrder(tree, 1);
}

运行结果如下：