数据结构：二叉树的基本运算

内容：构建二叉树的二叉链表存储结构，实现二叉树的创建、二叉树的先序/中序/后序递归遍历、统计二叉树的高度、统计结点的个数、叶子结点的个数、先序/中序非递归遍历、层序遍历等运算。

要求：

（1）二叉树中数据元素的类型统一抽象表示为ElemType类型，在程序中将ElemType类型具体化为char类型或其它类型

（2）基于栈实现二叉树的先序/中序非递归遍历
（3）基于队列实现二叉树的层序遍历

VS2019环境：

头文件“queue.h”：

#pragma once
#include
typedef struct qn {
	selemtype data[maxsize];//Bitree的指针
	int front;
	int rear;
}linkqn;
int initqueue(linkqn* p) {
	p->front = p->rear = 0;
	return 1;
}
int Qisfull(linkqn* p) {
	if (p->front - p->rear == maxsize - 1) {
		return 1;
	}
	return 0;
}
int Qisempty(linkqn* p) {
	if (p->front == p->rear) {
		return 1;
	}
	return 0;
}
void enterqueue(linkqn* p, selemtype x) {
	if (Qisfull(p)) { printf("队满，无法入队n"); return; }
	p->data[p->rear] = x;
	p->rear = (p->rear + 1 + maxsize) % maxsize;
}
void deletequeue(linkqn* p, selemtype* q) {
	//int i;
	if (Qisempty(p)) { printf("队空，无法出队n"); return; }
	*q = p->data[p->front];
	p->front = (p->front + 1 + maxsize) % maxsize;
	//return i;
}
elemtype Qfront(linkqn* p) {
	if (Qisempty(p)) {
		printf("队空，无法读取n");
	}
	return p->front;
}
elemtype Qrear(linkqn* p) {
	if (Qisempty(p)) {
		printf("队空，无法读取n");
	}
	return p->rear;
}

头文件：“stack.h”：

#pragma once
#include


int Sinit(sqstack* p) {
	p->top = -1;
	return 1;
}
int Sisempty(sqstack* p) {
	if (p->top == -1) {
		return 1;
	}
	return 0;
}
int Sisfull(sqstack* p) {
	if (p->top == maxsize - 1) {
		return 1;
	}
	return 0;
}
void Spush(sqstack* p, selemtype t) {
	if (Sisfull(p)) { printf("栈满，无法入栈"); }
	p->top++;
	int i = p->top;
	p->stack[i] = t;
}
void Spop(sqstack* p,selemtype *q) {
	if (Sisempty(p)) { printf("栈空，无法出栈n"); return; }
	*q = p->stack[p->top];
	p->top--;
}
selemtype Stop(sqstack* p) {
	return p->stack[p->top];
}

源文件：

#include
#include

#define maxsize 20
typedef char elemtype;
typedef struct tree{
	elemtype Data;
	struct tree* lchild;
	struct tree* rchild;
	elemtype tag;
}Bitree,*Binode;
typedef Binode selemtype;
typedef struct Stack {
	selemtype stack[maxsize];
	int top;
}sqstack;

#include"stack.h"
#include"queue.h"
selemtype create();
void Porder(selemtype t);
void Iorder(selemtype t);
void Psorder(selemtype t);
int Depth(selemtype t);
int count(selemtype t);
int leaves(selemtype t);
void swap(selemtype t);
void Porder1(selemtype t);
void Iorder1(selemtype t);
void Psorder1(selemtype t);
void Level(selemtype t);

int main() {
	//Bitree tr;
	selemtype t;
	t= create();
	
	printf("nPreOrder   "); Porder(t);
	printf("nInOrder    "); Iorder(t);
	printf("nPostOrder   "); Psorder(t);
	printf("nPreOrder1   "); Porder1(t);
	printf("nInOrder1   "); Iorder1(t);
	printf("nPostOrder1   "); Psorder1(t);
	printf("nDepth:   "); printf("%d", Depth(t));
	printf("nCount:   "); printf("%d", count(t));
	printf("nLeaves:   "); printf("%d", leaves(t));
	printf("nLevel:   "); Level(t);
	return 0;
}


void Psorder1(selemtype t) {//非递归后续
	sqstack s;
	Bitree *p;
	Sinit(&s);
	do {
		while (t) {
			t->tag = 'L';
			Spush(&s, t);
			t = t->lchild;
		}
		while (!Sisempty(&s) && s.stack[s.top]->tag == 'R') {
			Spop(&s, &p); 
			printf("%c    ", p->Data);
		}
		if (!Sisempty(&s)) {
			s.stack[s.top]->tag = 'R';
			t = s.stack[s.top]->rchild;
		}
	} while (!Sisempty(&s));
}
void Iorder1(selemtype t) {//非递归中序
	sqstack s;
	Bitree* p;
	Sinit(&s);
	while (s.top  || t) {
		if (t) {
			Spush(&s, t);
			t = t->lchild;
		}
		else { 
			Spop(&s, &p); 
			printf("%c    ", p->Data); 
			t = p->rchild;//创建指针，没有指向的地方，或者未初始化，不能用函数调用，但是创建变量有明确的地址 
		}
	}
}

void Porder1(selemtype t) {//非递归先序
	sqstack s;
	Bitree *p;
	Sinit(&s);
	while (s.top || t) {
		if (t) {
			printf("%c    ", t->Data);
			Spush(&s, t);
			t = t->lchild;
		}
		else { Spop(&s, &p);
		t = p->rchild; 
		}
	}
}


selemtype create() { //初始化树
	elemtype ch;
	selemtype t;
	scanf_s("%c", &ch, 1);
	if (ch != '#') {
		t = (selemtype)malloc(sizeof(Bitree));
		t->Data = ch;
		t->lchild = create();
		t->rchild = create();
	}
	else {
		t = NULL;
		//t->Data = NULL;
	}
	return t;
}

void Porder(selemtype t) {//递归先序
	if (t)
	{
		printf("%c  ", t->Data);
		Porder(t->lchild);
		Porder(t->rchild);
	}
	return;
}

void Iorder(selemtype t) {//递归中序
	if (t)
	{
		Porder(t->lchild);
		printf("%c  ", t->Data);
		Porder(t->rchild);
	}
	return;
}

void Psorder(selemtype t) {//递归后序
	if (t)
	{
		Psorder(t->lchild);
		printf("%c  ", t->Data);
		Psorder(t->rchild);
	}
	return;
}

int Depth(selemtype t) {//深度
	int y1,y2,y;
	if (t) {
		y1 = Depth(t->lchild);
		y2 = Depth(t->rchild);
		y = (y1 > y2 ? y1 : y2) + 1;
	}
	else y = 0;
	return y;
}

int count(selemtype t) {//结点数
	if (t) {
		return 1 + count(t->lchild) + count(t->rchild);
	}
	else return 0;
}

int leaves(selemtype t) {//叶结点数
	if (t) {
		return leaves(t->lchild) + leaves(t->rchild);
	}
	else return 1;
}

void swap(selemtype t) {//左右子树交换
	Bitree *p;
	if (t->lchild || t->rchild) {
		p = t->lchild;
		t->lchild = t->rchild;
		t->rchild = p;
		swap(t->lchild);
		swap(t->rchild);
	}
	return;
}
void Level(selemtype t) {
	linkqn q;
	selemtype p;
	initqueue(&q);
	printf("%c", t->Data); 
	enterqueue(&q, t);
	while (!Qisempty(&q)) {
		deletequeue(&q, &p);
		if (p->lchild) {
			printf("%c", p->lchild->Data);
			enterqueue(&q, p->lchild);
		}
		if (p->rchild) {
			printf("%c", p->rchild->Data);
			enterqueue(&q, p->rchild);
		}
	}
	
}