二叉树的递归和非递归实现前序、中序、后序、层次遍历

二叉树的遍历方式一般有前序、中序、后序三种方式。其中每种方式都可以由递归和非递归实现，非递归主要借助于栈来实现，还可以借助队列实现层级遍历。下面的代码在vs2019编译通过，其中的栈和队列是自己简单实现的。实现思路和代码如下：

#include <iostream>
#define  _CRT_SECURE_NO_WARNINGS
#define  STACK_SIZE 100
#define  QUEUE_SIZE 100


typedef struct Btree {
	char data;
	struct Btree* lChild;
	struct Btree* rChild;
}Btree, *PBtree;

//循环队列
class Myqueue
{
private:
	PBtree queue[QUEUE_SIZE];
	int front, rear;

public:
	Myqueue()
	{
		rear = front = 0;
	}

	bool IsEmpty()
	{
		return rear == front ? true : false;
	}

	bool enQueue(const PBtree T)
	{
		if ((rear + 1) % QUEUE_SIZE == front) 
		{
			return false;
		}
		queue[rear] = T;
		rear = (rear + 1) % QUEUE_SIZE;
		return true;
	}

	PBtree deQueue()
	{
		if ( rear == front)
		{
			return NULL;
		}
		PBtree p = queue[front];
		front = (front + 1) % QUEUE_SIZE;	
		return p;
	}

};

//栈
class MyStack
{
private:
	PBtree stack[STACK_SIZE];
	int top;
public:
	MyStack()
	{
		top = -1;
	}

	bool IsEmpty()
	{
		return -1 == top ? true : false;
	}

	bool push(const PBtree T)
	{
		if (STACK_SIZE - 1 == top )
		{
			return false;
		}
		stack[++top] = T;
		return true;
	}

	PBtree pop()
	{
		if (-1 == top)
		{
			return NULL;				 
		}
		return stack[top--];
	}

};


//采用前序创建二叉树
void CreateTree(PBtree *T)
{
    char data;
	scanf_s("%c", &data);
	if (data == '#')
	{
		*T = NULL;
		return;
	}
	else
	{
		*T = (PBtree)malloc(sizeof(Btree));
		if (!*T)
		{
			exit(-1);
		}
		(*T)->data = data;
		CreateTree(&(*T)->lChild);
		CreateTree(&(*T)->rChild);
	}
}

//递归前序遍历 
//比较简单 按照根-左-右顺序访问即可
void PreOrder(PBtree T)
{
	if (T)
	{
		printf("--%c--", T->data);
		PreOrder(T->lChild);
		PreOrder(T->rChild);
	}
}

//非递归前序遍历
//思路：初始将根节点入栈，栈不空就继续循环，出栈访问栈顶元素（根结点），再看右子树
//不空入栈，再看左子树，不空入栈（根据栈先入后出的特点）
void PreOrderNoRecursion(const PBtree T)
{
	if (!T) return;
	MyStack stack;
	PBtree p = T;
	stack.push(p);
	while (!stack.IsEmpty())
	{
		p = stack.pop();
		printf("--%c--", p->data);
		if (p->rChild)
		{
			stack.push(p->rChild);
		}
		if (p->lChild)
		{
			stack.push(p->lChild);
		}
	}

}

//递归中序遍历
//左-根-右
void InOrder(PBtree T)
{
	if(T)
	{
		InOrder(T->lChild);
		printf("--%c--", T->data);
		InOrder(T->rChild);
	}
}


//非递归中序遍历
//思路：左子树入栈遍历到最左边，栈不空，则退栈访问栈顶元素(根结点)，再将右子树入栈
//继续循环，注意循环条件为栈不空或者指针不空
void InOrderNoRecursion(const PBtree T)
{
	MyStack stack;
	PBtree p = T;

	while (!stack.IsEmpty() || p != NULL)
	{
		while(p) //if(p) 
		{
			stack.push(p);
			p = p->lChild;
		}
		if(!stack.IsEmpty())//else  
		{
			p = stack.pop();//
            printf("--%c--", p->data);
			p = p->rChild;
		}			
	}
}

//递归后序遍历
//左-右-根
void PostOrder(PBtree T)
{
	if (T)
	{
		PostOrder(T->lChild);
		PostOrder(T->rChild);
		printf("--%c--", T->data);
	}
}

//非递归后序遍历（方法较多，这里选取最容易理解的一种）
//非递归后序遍历和非递归前序遍历存在联系，仔细观察可以得到如下规律：
//1栈：调整前序非递归遍历的入栈顺序为  先左后右
//2栈：将前序遍历的访问操作存入2栈，然后输出2栈即可
void PostOrderNoRecursion(const PBtree T)
{
	if (!T) return;
	MyStack stack1;
	MyStack stack2;
	
	PBtree p = T;
	stack1.push(p);

	while (!stack1.IsEmpty())
	{
		p = stack1.pop();
		stack2.push(p);

		if (p->lChild)
		{
			stack1.push(p->lChild);
		}
		if (p->rChild)
		{
			stack1.push(p->rChild);
		}
	}
	
	while (!stack2.IsEmpty())
	{
		p = stack2.pop();
		printf("--%c--", p->data);
	}

}


//层次遍历,借助队列实现
//根先入队，出队访问，并按照从左到右依次将子树入队即可，队空退出循环
void LevelOrder(const PBtree T)
{
	Myqueue queue;
	PBtree p = T;
	queue.enQueue(p);
	while (!queue.IsEmpty())
	{
		p = queue.deQueue();
		printf("--%c--", p->data);
		if (p->lChild)
		{
			queue.enQueue(p->lChild);
		}
		if (p->rChild)
		{
			queue.enQueue(p->rChild);
		}
	}
}


int main()
{
	printf("please input string in PreOrder(# is null)!\n");
	//abc##d##e#f##
    /*            a
	            /   \
        	   b     e
 	          / \     \
	         c   d     f                   
    */

	PBtree T;
	CreateTree(&T);

	printf("\n PreOrder-Recursion:\n");
	PreOrder(T);
    printf("\n PreOrder-No-Recursion:\n");
	PreOrderNoRecursion(T);
	
	printf("\n InOrder-Recursion:\n");
	InOrder(T);
	printf("\n InOrder-No-Recursion:\n");
	InOrderNoRecursion(T);

	printf("\n PostOrder-Recursion:\n");
	PostOrder(T);
	printf("\n PostOrder-No-Recursion:\n");
	PostOrderNoRecursion(T);

	printf("\n LevelOrder:\n");
	LevelOrder(T);

	return 0;
}