二叉树递归遍历，非递归遍历，层次遍历代码实现

二叉树递归遍历，非递归遍历，层次遍历代码实现 二叉树递归遍历算法：

对如下的二叉树进行遍历，不同遍历有不同的顺序，代码如下

--------------------------------------------------先序中序后序遍历---------------------------------------------------------------

#include 
typedef struct Tnode {
	cElemType data;
	struct Tnode* lchild, * rchild;
}Tnode,*Pnode;
typedef struct Tstack {
	Pnode Node;
}Tstack;
void CreateTree(Pnode* Thead)//此时传递的是指针的指针
{						     //在函数内部可以实现修改实参指针的地址，
	cElemType tdata;		 //而如果只是传递一个指针，那么修改的是形参的地址，函数结束后地址变回去
	cout << "输入一个数据" << endl;
	cin >> tdata;
	if (tdata == '#')
	{
		*Thead = NULL;
	}
	else
	{
		*Thead = (Tnode*)malloc(sizeof(Tnode));
		if (!*Thead)
		{
			cout << "空间分配失败" << endl;
			exit(OVERFLOW);
		}
		(*Thead)->data = tdata;
		CreateTree(&(*Thead)->lchild);
		CreateTree(&(*Thead)->rchild);
	}
}
//先序遍历
//前中后序遍历的区别在于输出数据的时机不同
void preOrderTraverse(Tnode* thead)
{
	if (thead==NULL)
	{
		return;
	}
	else
	{
		cout << thead->data <<"  ";
		preOrderTraverse(thead->lchild);
		preOrderTraverse(thead->rchild);
	}
}
//中序遍历
void midOrderTraverse(Tnode* thead)
{
	if (thead == NULL)
	{
		return;
	}
	else
	{
		midOrderTraverse(thead->lchild);
		cout << thead->data << "  ";
		midOrderTraverse(thead->rchild);
	}
}
//后序遍历
void postOrderTraverse(Tnode* thead)
{
	if (thead == NULL)
	{
		return;
	}
	else
	{
		postOrderTraverse(thead->lchild);
		postOrderTraverse(thead->rchild);
		cout << thead->data << "  ";
	}
}
int main()
{
	Tnode* thead=(Tnode*)malloc(sizeof(Tnode));
	CreateTree(&thead);
	cout << "先序遍历" << endl;
	preOrderTraverse(thead);
	cout << endl<<"中序遍历" << endl;
	midOrderTraverse(thead);
	cout << endl<< "后序遍历" << endl;
	postOrderTraverse(thead);
}

-------------------------------------------------------非递归遍历(使用栈)-----------------------------------------------------

#include 
typedef struct Tnode {
	cElemType data;
	struct Tnode* lchild, * rchild;
}Tnode, * Pnode;
typedef struct Tstack {
	Tnode tstack[MAXSIZE];
	int length;
}Tstack,*Pstack;
void InitTreeStack(Pstack pstack) {
	pstack->length = 0;
}
void PushTreeNode(Pnode node,Pstack ts)
{
	if (ts->length >= MAXSIZE) {
		cout << "stack is full" << endl;
		exit(OVERFLOW);
	}
	ts->tstack[ts->length++] = *node;
}
void PopTreeNode(Pnode node, Pstack ts)
{
	if (ts->length == 0) {
		cout << "stack is empty" << endl;
		exit(ERROR);
	}
	*node = ts->tstack[ts->length - 1]; //数组中是一个Tnode类型数据
	ts->length--;
}
bool TreeStackEmpty(Pstack ts)
{
	if (ts->length == 0)
		return TRUE;
	else
		return FALSE;
}
void MidOrderTraverse(Pnode node)
{
	Pnode p = node;
	Pnode q=(Pnode)malloc(sizeof(Tnode));
	Pstack s = (Pstack)malloc(sizeof(Tstack));
	InitTreeStack(s);
	while (p || !TreeStackEmpty(s))
	{
		if (p) {
			PushTreeNode(p,s);
			p = p->lchild;
		}
		else {
			PopTreeNode(q, s);
			cout << q->data;
			p = q->rchild;
		}
	}
}
void CreateTree(Pnode* Thead)//此时传递的是指针的指针
{						     //在函数内部可以实现修改实参指针的地址，
	cElemType tdata;		 //而如果只是传递一个指针，那么修改的是形参的地址，函数结束后地址变回去
	cout << "输入一个数据" << endl;
	cin >> tdata;
	if (tdata == '#')
	{
		*Thead = NULL;
	}
	else
	{
		*Thead = (Tnode*)malloc(sizeof(Tnode));
		if (!*Thead)
		{
			cout << "空间分配失败" << endl;
			exit(OVERFLOW);
		}
		(*Thead)->data = tdata;
		CreateTree(&(*Thead)->lchild);
		CreateTree(&(*Thead)->rchild);
	}
}

int main()
{
	Tnode* thead = (Tnode*)malloc(sizeof(Tnode));
	CreateTree(&thead);
	MidOrderTraverse(thead);
}

------------------------------------------------层次遍历(使用队列)--------------------------------------------------------------

#include 
typedef struct Tnode {
	cElemType data;
	Tnode* lchild, * rchild;
}Tnode,*Pnode;
typedef struct Tqueue {
	Tnode tqueue[MAXSIZE];
	int front;
	int rear;
}Tqueue,*Pqueue;
void InitTreeQueue(Pqueue p)
{
	p->front = 0;
	p->rear = 0;
}
void PushTreeQueue(Pqueue q, Pnode node)//队尾插入元素 最多能插入MAXSIZE-1个数据
{
	if ((q->rear + 1) % MAXSIZE == q->front)//队列满
	{
		cout << "队列已满" << endl;
		exit(OVERFLOW);
	}
	q->tqueue[q->rear] = *node;
	q->rear = (q->rear + 1) % MAXSIZE;//指针后移
}
void PopTreeQueue(Pqueue q, Pnode p)//删除队头元素
{
	if (q && (q->front == q->rear))
	{
		cout << "队列为空" << endl;
		exit(OVERFLOW);
	}
	*p = q->tqueue[q->front];
	q->front = (q->front + 1) % MAXSIZE; //头指向下一个数据
}
void CreateTree(Pnode* thead)//可以看成Tnode的二级指针
{
	//二级指针满足 Pnode p;  Tnode t; p = *thead; (*(*thead)).data = '1';
	cElemType tdata;
	cout << "输入数据" << endl;
	cin >> tdata;
	if (tdata == '#')
	{
		*thead = NULL;
	}
	else
	{
		*thead = (Tnode*)malloc(sizeof(Tnode));
		if (!*thead)
		{
			cout << "空间分配失败" << endl;
			exit(OVERFLOW);
		}
		(*thead)->data = tdata;
		CreateTree(&(*thead)->lchild);
		CreateTree(&(*thead)->rchild);
	}
}
bool TreeQueueEmpty(Pqueue q)
{
	if ((MAXSIZE - q->front + q->rear) % MAXSIZE != 0) //非空
		return FALSE;
	else
		return TRUE;
		
}
void MidOrderTraverse(Pnode node)
{
	Pnode p=(Pnode)malloc(sizeof(Tnode));
	Pqueue queue = (Pqueue)malloc(sizeof(Tqueue));
	InitTreeQueue(queue);
	PushTreeQueue(queue, node);
	while (!TreeQueueEmpty(queue))
	{
		PopTreeQueue(queue, p);
		cout << p->data << "  ";
		if (p->lchild != NULL) {
			PushTreeQueue(queue, p->lchild);
		}
		if (p->rchild != NULL) {
			PushTreeQueue(queue, p->rchild);
		}
	}
}
int main() 
{
	Pnode thead = (Pnode)malloc(sizeof(Tnode));
	CreateTree(&thead);
	MidOrderTraverse(thead);
}