/*郭睿玥第七次算法实验作业*/

/*实验原理
二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。
遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。
若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。
若规定先左后右，则只有前三种情况，分别是：
DLR——先(根)序遍历。
LDR——中(根)序遍历。
LRD——后(根)序遍历。
对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。
递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。
而非递归算法中的控制是由设计者定义和使用堆栈来实现的。
*/

/*实验环境
CodeBlocks*/


/*实验目的
掌握二叉树的二叉链存储结构及表示。
掌握二叉树的三种遍历算法（递归和非递归两类）。
运用三种遍历的方法求解二叉树的有关问题。
*/



/*实验内容
实现二叉树的二叉链表存储结构；
1. 创建一颗二叉树
2.递归前序遍历二叉树
3.递归中序遍历二叉树
4.递归后序遍历二叉树
5. 测试递归打印二叉树代码
6. 非-递归前序遍历二叉树
7. 非-递归实现中序遍历二叉树
8. 非 - 递归实现后序遍历【较为复杂的方法】
9. 非 - 递归实现后序遍历【简单的方法】
10. 二叉树的层次遍历
*/

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100//定义二叉树最大节点数为100


// 二叉树的实现

// 定义 二叉树的 结构体
typedef struct node{//二叉树结构体
	char data;//数据域
	struct node *left;//指向左子树的指针
	struct node *right;//指向右子树的指针
}Node, *Tree;//类型别名

// 依据前序遍历创建二叉树
// 根左右：ABF##CD##E###

Tree create_tree(){// 创建二叉树
	Node *root = NULL;//初始化根节点
	char ch;//定义字符
	scanf("%c", &ch); // 输入 ABF##CD##E###

	if (ch != '#'){//如果该节点不是空的则执行
		root = (Node*)malloc(sizeof(Node));//申请空间
		root->data = ch;//该节点的数据为输入的字符
            //前序递归创建二叉树
		root->left = create_tree(); // 递归创建左子树
		root->right = create_tree();//递归创建右子树
	}
	else{//如果输入的是#则表示该节点为空
		root = NULL;//该节点为空
	}

	return root;//返回根节点方便调用
}


// 递归前序遍历二叉树
void preOrderRec(Tree root){//前序递归调用
	if (root != NULL){//若该二叉树不是空树，则执行
		printf(" %c - ", root->data);//输出数据
		preOrderRec(root->left);//递归输出左子树
		preOrderRec(root->right);//递归输出右子树
	}
}

void preOrderNRec(Tree root){ // 非-递归前序遍历二叉树
	Tree stack[MAXSIZE], node;//创建一个数组这个数组在这个程序中可以近似一个栈，定义一个树节点，之后会通过这个节点的移动来按照前序来遍历二叉树
	int top = 0;//栈顶指针

	if (root == NULL){//判断是否是空树
		printf("tree is empty-- \n");//如果是空树则输出
		return;//函数结束，无返回值
	}
	else{//如果不是空树则执行
		top++;//栈顶指针加一
		// 仿照一个栈
		stack[top] = root; // 将根节点入栈
		while (top > 0){//如果没有全部出栈，则出栈
			//出栈
			node = stack[top--];//则使该节点为栈顶节点
			printf(" %c - ", node->data);//输出该节点数据域

			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
			if (node->right != NULL){//判断该节点的右子树是否为空
				stack[++top] = node->right;  // 如果不是空节点则入栈以实现前序遍历
			}
			if (node->left != NULL){//判断该节点的左子树是否为空
				stack[++top] = node->left;// 如果不是空节点则入栈以实现前序遍历
			}

		}

	}
}


// 递归中序遍历二叉树
void inOrderRec(Tree root){//中序递归调用
	if (root != NULL){//若该二叉树不是空树，则执行
		inOrderRec(root->left);//递归输出左子树
		printf(" %c - ", root->data);//输出数据
		inOrderRec(root->right);//递归输出右子树
	}
}

// 非-递归实现中序遍历二叉树
void inOrderNRec(Tree root){// 非-递归实现中序遍历二叉树，参数为根节点
	Tree stack[MAXSIZE], node;//创建一个数组这个数组在这个程序中可以近似一个栈，定义一个树节点，之后会通过这个节点的移动，来按照前序来遍历二叉树
	int top = 0;//
	// 判断树是否为空
	if (root == NULL){//判断是否是空树
		printf("tree is empty-- \n");//如果是空树则输出
		return;//函数结束，无返回值
	}
	node = root;//使node节点被赋值为根节点

	while (node != NULL || top > 0){//如果该节点不是空节点并且定义的栈不是经过一系列操作以后没有全部出栈则继续执行循环

		// 将所有的左子树节点入栈
		while (node != NULL){//判断该节点是否是空节点，直到左子树是空
			stack[++top] = node;//如果不是空节点则入栈
			node = node->left;//移动节点到左孩子
		}
		//  如果右节点为空的话，执行下列语句
		node = stack[top--];//使该节点为栈顶指针
		printf(" %c - ", node->data);//输出栈顶指针

		// 扫描右节点
		node = node->right;//指向右节点
	}

}


// 递归后序遍历二叉树
void backOrderRec(Tree root){//后序递归调用
	if (root != NULL){//若该二叉树不是空树，则执行
		backOrderRec(root->left);//递归输出左子树
		backOrderRec(root->right);//递归输出右子树
		printf(" %c - ", root->data);//输出数据

	}
}

// 非 - 递归实现后序遍历
void backOrderNRec(Tree root){//非 - 递归实现后序遍历

	Node *p = root;//
	Node *stack[MAXSIZE];//创建栈这栈用来存储节点
	int num = 0;//栈顶指针
	Node *have_visited = NULL;//

	while (NULL != p || num>0)//创建一个数组这个数组在这个程序中可以近似一个栈，定义一个树节点，之后会通过这个节点的移动，来按照前序来遍历二叉树
	{
		while (NULL != p)//判断节点是否为空如果不是空，则继续循环，该节点的数据入栈，指针指向左孩子
		{
			stack[num++] = p;//数据入栈
			p = p->left;//移动指针
		}
		p = stack[num - 1];//取栈顶指针
		if (NULL == p->right || have_visited == p->right)//如果该节点的左孩子不为空并且已经调用过该节点的左孩子则可以输出该节点的值
		{
			printf(" %c - ", p->data);//打印该节点的数据
			num--;//出栈
			have_visited = p;//表示p已经出栈
			p = NULL;//p置空
		}
		else//如果没有调用过该节点
		{
			p = p->right;//移动指针到左孩子
		}
	}

}

void backOrderNRecSimple(Tree root){//非 - 递归实现后序遍历的方法二
	Tree stack[MAXSIZE], node;
	int top = 0;//栈顶指针
	int count = 0;//标志变量
	char array[MAXSIZE]; // 使用一个数组来保存数据，方便最后数组的反转

	if (root == NULL){//如果是空栈
		printf("tree is empty-- \n");//提示语句
		return;//返回
	}
	else{
		top++;// 仿照一个栈
        stack[top] = root; // 将根节点入栈
		while (top > 0){
			//出栈
			node = stack[top--];//赋值
			array[count++] = node->data; // 将其保存在一个数组当中

			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
			if (node->left != NULL){//如果左子树不是空的
				stack[++top] = node->left;  // 入栈
			}
			if (node->right != NULL){//如果右子树不是空的
				stack[++top] = node->right;// 入栈
			}

		}

	}
	// 反转数组，输出
	for (int i = count-1; i >= 0; i--){//数组的顺序就是后序遍历的顺序
		printf(" %c - ", array[i]);//逐个输出
	}

}

// 层次遍历，打印出二叉树的值
/*
算法语言描述如下；
如果不是空树
则 1.根节点入队，通过
   2.
*/
void Level_traversal(Tree root){//层次遍历函数

	if (root == NULL){//判断是否是空树
		printf("tree is empty-- \n");//是空树则显示是空的
		return;//返回主函数
	}

	Tree stack[MAXSIZE], node;//数组stack来模拟队列，改变node来输出节点的值和入队
	node = root;//首先使node被赋值为根节点
	int front = 0;  // 队首指针
	int rear = 0;//队末指针

	stack[rear++] = node;//根节点入队

	while (front != rear){//只要不是空队则使节点按层入队最后出队

		node = stack[front++];//使node为队首节点
		printf(" %c - ", node->data);//输出节点数据

		// 左右子树入队列，由于入队是按层入得队所以移动队首可以按层序找到上一层的每个节点，通过节点可以找到该节点的左右孩子
		if (node->left != NULL){//看node节点的左节点是不是空的如果不是空的入队
			stack[rear++] = node->left;//左孩子入队
		}

		if (node->right != NULL){//看node节点的右节点是不是空的如果不是空的入队
			stack[rear++] = node->right;//右孩子入队
		}
	}

}


int main(){

	printf("starting ------ \n");//提示开始


	Tree root = create_tree();//创建树
	printf("递归前序遍历--- \n");//提示调用递归前序遍历
	preOrderRec(root);//递归前序遍历
	printf("\n");//空行
	printf("递归中序遍历--- \n");//提示调用递归中序遍历
	inOrderRec(root);//递归中序遍历
	printf("\n");//空行
	printf("递归后序遍历--- \n");//提示调用递归后序遍历
	backOrderRec(root);//递归后序遍历
	printf("\n");//空行
	printf("------------------\n");//提示

	printf("非递归实现前序遍历--- \n");//提示调用非递归前序遍历
	preOrderNRec(root);//调用非递归前序遍历
	printf("\n");//空行

	printf("非递归实现中序遍历--- \n");//提示调用非递归中序遍历
	inOrderNRec(root);//调用非递归中序遍历
	printf("\n");//空行

	printf("非递归实现后序遍历--- \n");//提示调用非递归后序遍历
	backOrderNRec(root);//调用非递归后序遍历
	printf("\n");//空行

	printf("非递归实现后序遍历  简单的方法 --- \n");//提示调用非递归后序遍历
	backOrderNRecSimple(root);//调用非递归后序遍历
	printf("\n");//空行

	printf("层次遍历 --- \n");//提示调用层次遍历
	Level_traversal(root);//调用层次遍历
	printf("\n");//空行

	return 0;//返回
}

/*
实验结果
starting ------
ABF##CD##E###
递归前序遍历---
 A -  B -  F -  C -  D -  E -
递归中序遍历---
 F -  B -  D -  C -  E -  A -
递归后序遍历---
 F -  D -  E -  C -  B -  A -
------------------
非递归实现前序遍历---
 A -  B -  F -  C -  D -  E -
非递归实现中序遍历---
 F -  B -  D -  C -  E -  A -
非递归实现后序遍历---
 F -  D -  E -  C -  B -  A -
非递归实现后序遍历  简单的方法 ---
 F -  D -  E -  C -  B -  A -
层次遍历 ---
 A -  B -  F -  C -  D -  E -

Process returned 0 (0x0)   execution time : 16.420 s
Press any key to continue.

 */