二叉树的实验代码

Mryan2005

大一下学期还是过去了，之前写的二叉树的实验代码，我决定还是共享出来吧。
以下是代码
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

// 枚举方向
typedef enum direction {Left, Right} direction;

// 队列结构体
typedef struct QueueNode {
	int data;
	struct QueueNode *next;
} QueueNode;
typedef struct Queue {
	QueueNode *head;
	QueueNode *tail;
} Queue;

// 树结构体
typedef struct treeNode {
	int data;
	struct treeNode *LChild;
	struct treeNode *RChild;
} treeNode, *tree;

// 栈结构体
typedef struct StackNode {
	treeNode *TreeNode;
	struct StackNode *next;
} StackNode, *Stack;

// 获取队头元素
int GetHead(Queue Q) {
	if(Q.head) return Q.head->data;
	else return 0;
}

// 出队
int DeQueue(Queue *Q) {
	if(Q->head == NULL) return 0;
	int data;
	QueueNode *q = Q->head;
	data = Q->head->data;
	Q->head = Q->head->next;
	if(!Q->head) Q->tail = Q->head;
	free(q);
	return data;
}

// 入队
void EnQueue(Queue *L, int data) {
	if(!L->head) {
		L->head = (QueueNode*)malloc(sizeof(QueueNode));
		L->head->data = data;
		L->head->next = NULL;
		L->tail = L->head;
	} else {
		L->tail->next = (QueueNode*)malloc(sizeof(QueueNode));
		L->tail = L->tail->next;
		L->tail->data = data;
		L->tail->next = NULL;
	}
}

// 入栈
void Push(Stack *S, treeNode *tNode) {
	StackNode *SN = (StackNode*)malloc(sizeof(StackNode));
	SN->TreeNode = tNode;
	if(!*S) {
		SN->next = NULL;
		(*S) = SN; 
	} else {
		SN->next = *S;
		*S = SN;
	}
}

// 出栈
treeNode *Pop(Stack *S) {
	if(*S) {
		treeNode *p = (*S)->TreeNode;
		StackNode *q = *S;
		(*S) = (*S)->next;
		free(q);
		return p;
	} else return NULL;
}

// 获取栈顶元素
treeNode *GetStackHead(Stack S) {
	if(S) {
		treeNode *p = S->TreeNode;
		return p;
	} else return NULL;
}

// 先序遍历
void readBinTreePre(tree BinTree) {
	if(!BinTree) {
		printf("这是一个空树");
		return;
	}
	treeNode *p = BinTree;
	Stack S = NULL;
	while(p || S) {
		if(p) {
			printf("%d ", p->data);
			Push(&S, p);
			p = p->LChild;
		} else p = Pop(&S)->RChild;
	}
}

// 中序遍历
void readBinTreeMiddle(tree BinTree) {
	if(!BinTree) {
		printf("这是一个空树");
		return;
	}
	treeNode *p = BinTree;
	Stack S = NULL;
	while(p || S) {
		if(p) {
			Push(&S, p);
			p = p->LChild;
		} else {
			p = Pop(&S);
			printf("%d ", p->data);
			p = p->RChild;
		}
	}
}

// 后序遍历
void PostOrder(tree BinTree) {
	if(!BinTree) {
		printf("这是一个空树");
		return;
	}
	treeNode *p = BinTree, *pLast = NULL;
	Stack S = NULL;
	Push(&S, p);
	while(p || S) {
		if(p && (p->RChild || p->LChild)) {
			if(p->RChild && pLast == p->RChild) {
				pLast = p;
				printf("%d ", pLast->data);
				Pop(&S);
				p = GetStackHead(S);
				continue;
			}
			if(p->LChild && pLast == p->LChild) {
				pLast = p;
				printf("%d ", pLast->data);
				Pop(&S);
				p = GetStackHead(S);
				continue;
			}
			if(p->RChild) Push(&S, p->RChild);
			if(p->LChild) Push(&S, p->LChild);
			p = p->LChild;
		} else if(p){
			pLast = p;
			printf("%d ", pLast->data);
			Pop(&S);
			p = GetStackHead(S);
		} else if(!p) p = GetStackHead(S);
	}
}

// 基于先序遍历的构造算法，创建二叉树。
void CreateABinTree(tree *BinTree, Queue *Q) {
	direction pos = Left;
	Stack S = NULL;
	treeNode *p, *q;
	while(S || Q->head) {
		if(!*BinTree) {
			p = (treeNode*)malloc(sizeof(treeNode));
			p->data = DeQueue(Q);
			p->LChild = p->RChild = NULL;
			*BinTree = q = p;
		} else if(GetHead(*Q)) {
			p = (treeNode*)malloc(sizeof(treeNode));
			p->data = DeQueue(Q);
			p->LChild = p->RChild = NULL;
			if(pos == Left) {
				q->LChild = p;
				Push(&S, q);
			} else {
				q->RChild = p;
				pos = Left;
			}
			q = p;
		} else if(pos == Left) {
			pos = Right;
			DeQueue(Q);
		} else if(pos == Right) {
			DeQueue(Q);
			q = Pop(&S);
		}
	}
}

// 摧毁二叉树
void destroyBinTree(tree *BinTree) {
	if(!BinTree) {
		printf("这是一个空树");
		return;
	}
	treeNode *p = *BinTree, *temp = p;
	Stack S = NULL;
	while(p || S) {
		if(p) {
			Push(&S, p);
			p = p->LChild;
		} else {
			temp = p = Pop(&S);
			p = p->RChild;
			free(temp);
		}
	}
	*BinTree = NULL;
}

// 计算二叉树结点总数
void countTreeNodes(tree BinTree) {
	int count = 0;
	treeNode *p = BinTree;
	Stack S = NULL;
	while(p || S) {
		if(p) {
			count++;
			Push(&S, p);
			p = p->LChild;
		} else p = Pop(&S)->RChild;
	}
	printf("%d\n", count);
}

// 计算二叉树叶子总数
void countLeafNodes(tree BinTree) {
	int count = 0;
	treeNode *p = BinTree;
	Stack S = NULL;
	while(p || S) {
		if(p) {
			Push(&S, p);
			p = p->LChild;
		} else if(GetStackHead(S)->RChild) p = Pop(&S)->RChild;
		else {
			if(!GetStackHead(S)->LChild && !GetStackHead(S)->RChild) count++;
			Pop(&S);
		}
	}
	printf("%d\n", count);
}

// 计算二叉树的深度
void countTreeDepth(tree BinTree) {
	int count = 0, countMax = 0;
	treeNode *p = BinTree;
	Stack S = NULL;
	while(p || S) {
		if(p) {
			count++;
			Push(&S, p);
			p = p->LChild;
		} else {
			p = Pop(&S);
			countMax = count > countMax? count: countMax;
			if(!p->RChild) count--;
			if(p == BinTree) count = 1;
			p = p->RChild;
		}
	}
	printf("%d\n", countMax);
}

// 交换各结点的左右子树，并用先序遍历新的二叉树
void f(tree BinTree) {
	if(!BinTree) {
		printf("这是一个空树");
		return;
	}
	treeNode *p = BinTree, *temp = NULL;
	Stack S = NULL;
	while(p || S) {
		if(p) {
			Push(&S, p);
		} else {
			p = Pop(&S);
			temp = p->LChild;
			p->LChild = p->RChild;
			p->RChild = temp;
		}
		p = p->LChild;
	}
}

// 清屏（我的遗憾）
void clearCMD() {
	COORD pos = {0,0};
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
	for(int i = 0; i < 10; i++) for(int i = 1; i <= 20; i++) printf("                   ");
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

int main() {
	char ch;
	int temp = 0, choice = 0, flag = 0;
	Queue L;
	L.tail = L.head = NULL;
	tree BiTree = NULL;
	while(1) {
		clearCMD();
		printf("\t\t二叉树操作\n");
		printf("\t=========================================\n");
		printf("\t\t1：建立二叉链表           \n"); //照此，补完整下面的菜单项
		printf("\t\t2：读取先序二叉链表           \n"); 
		printf("\t\t3：读取中序二叉链表           \n"); 
		printf("\t\t4：读取后序二叉链表           \n"); 
		printf("\t\t5：计算二叉树结点总数           \n"); 
		printf("\t\t6：计算二叉树叶子总数           \n"); 
		printf("\t\t7：计算二叉树的深度           \n"); 
		printf("\t\t8：交换各结点的左右子树，并用先序遍历新的二叉树           \n"); 
		printf("\t\t9：摧毁二叉树\n");
		printf("\t\t0：退出                   \n");
		printf("\t请选择：");
		while(1) {
			ch = getchar();
			if(ch == '\n' && !flag) {
				choice = -1;
				goto out;
			} else if(ch == '\n') break;
			choice += ch-'0';
			choice *= 10;
			flag = 1;
		}
		choice /= 10;
		out:;
		clearCMD();
		switch(choice) {
		case 1:
			if(!BiTree) {
				printf("请输入要输入的数据\n");
				while((ch = getchar()) != '\n') {
					if(ch != ' ') {
						temp += ch-'0';
						temp *= 10;
					} else {
						EnQueue(&L, temp/10);
						temp = 0;
					}
				}
				CreateABinTree(&BiTree, &L);
			} else {
				printf("树已存在");
				printf("\n");
			}
			break;
		case 2:
			printf("先序序列为: ");
			readBinTreePre(BiTree);
			printf("\n");
			break;
		case 3:
			printf("中序序列为: ");
			readBinTreeMiddle(BiTree);
			printf("\n");
			break;
		case 4:
			printf("后序序列为: ");
			PostOrder(BiTree);
			printf("\n");
			break;
		case 5:
			printf("二叉树结点总数为: ");
			countTreeNodes(BiTree);
			break;
		case 6:
			printf("二叉树叶子总数为: ");
			countLeafNodes(BiTree);
			break;
		case 7:
			printf("二叉树的深度为: ");
			countTreeDepth(BiTree);
			break;
		case 8:
			f(BiTree);
			readBinTreePre(BiTree);
			printf("\n");
			break;
		case 9:
			destroyBinTree(&BiTree);
			printf("树已摧毁\n");
			break;
		case 0:
			printf("Goodbye! see you next time!");
			exit(0);
			break;
		default:
			printf("\n============================= Warning! ===================================\n");
			printf("Sorry! I don't know what you choose, please input your choice again.\n");
			printf("==========================================================================\n");
			break;
		}
		printf("本次操作结束，请按一下Enter键以继续操作。");
		getchar();
		choice = 0;
		flag = 0;
	}
}
注意：不要直接复制粘贴
[链接登录后可见]