引言

????二叉树的遍历方法有：前序遍历、中序遍历、后序遍历、层序遍历，其中前中后序遍历又有递归遍历和非递归遍历之分。
????由于递归遍历算法本质上是借助系统栈实现的，因此，其非递归遍历算法的实现，也需要借助栈来实现。
????对于层序遍历，因为是从根节点开始向下逐层、从左向右遍历的，要求最先遍历到的结点先被访问，即“先进先出”的一种特性，就可以借助一个队列完成层序遍历。
????下面，先分别准备栈和队列两种数据结构的链式存储实现类（ PS：此次使用C++语言编写代码，这样整体代码结构比较清晰，方法调用时候引用传值比较nice，有关一些基本操作的函数/方法管理起来也更加方便些，以下代码复制粘贴过去即可用）。

0 有关线性表结点定义-LinkNode

????LinkNode结点定义本来是放置在一个单独的头文件#include "LinkNode.h"里面的，采用类模板方式定义，是可以线性表通用的，被但是后来考虑到在树的一些操作过程中，需要同时在一个头文件里面引入栈和队列，为了偷懒，就直接将结点类作为栈和队列的内部类进行管理了。
????结点定义代码如下，

//结点定义
template <typename T>
class LinkNode{
public:
	//setter
	void setData(T data){
		this->data=data;
	}
	void setNext(LinkNode* next){
		this->next=next;
	}
	//getter
	T getData(){
		return this->data;
	}
	LinkNode<T>* getNext(){
		return this->next;
	}
	//constructor
	LinkNode(){
		this->setData(0);
		this->setNext(NULL);
	}
	LinkNode(T data,LinkNode* next){
		this->setData(0);
		this->setNext(NULL);
	}

protected:

private:
	T data;//数据域
	LinkNode* next;//指针域
};

1 栈的链式存储结构实现-LinkedStack

????直接上代码，不解释原理。


//#include "LinkNode.h"
/**
* 链式栈
*/
template <typename T>
class LinkedStack{
public:
	//inner class
	template <typename T>
	class LinkNode{
	public:
		//setter
		void setData(T data){
			this->data=data;
		}
		void setNext(LinkNode* next){
			this->next=next;
		}
		//getter
		T getData(){
			return this->data;
		}

		LinkNode<T>* getNext(){
			return this->next;
		}
		//constructor
		LinkNode(){
			this->setData(0);
			this->setNext(NULL);
		}
		LinkNode(T data,LinkNode* next){
			this->setData(0);
			this->setNext(NULL);
		}

	protected:

	private:
		T data;//数据域
		LinkNode* next;//指针域
	};

	//setter
	void setHeader(LinkNode<T>* header){
		if (this->header!=NULL)
		{
			this->header=header;
			return;
		}
		std::cout<<"do setHeader Failed!"<<std::endl;
	}
	//getter
	LinkNode<T>* getHeader(){
		return this->header;
	}
	//constructor
	LinkedStack(){
		this->header=new LinkNode<T>;
	}

	//methods
	/**
	* 判断栈空
	*/
	bool isEmpty(){
		return this->header->getNext()==NULL?true:false;
	}

	/**
	 * 获取栈顶元素
	 */
	LinkNode<T>* getTop(){
		return this->header->getNext();
	}

	/**
	* 进栈[头插法-先进后出]
	*/
	bool PushLinkedStack(T e){
		//创建新的结点
		LinkNode<T>* newNode=NULL;
		newNode=new LinkNode<T>;
		newNode->setData(e);
		//入栈操作
		newNode->setNext(this->header->getNext());
		this->header->setNext(newNode);
		return true;
	}

	/**
	* 出栈[头删法-后进先出]
	*/
	bool PopLinkedStack(T& e){
		LinkNode<T>* p=NULL;//辅助指针
		//获取被删除的结点
		p=this->header->getNext();
		//出栈
		this->header->setNext(p->getNext());
		//销毁结点
		if (p!=NULL)
		{
			e=p->getData();
			delete p;
		}
		return true;
	}

protected:

private:
	LinkNode<T>* header;//头结点
};

2 队列的链式存储结构实现-LinkedQueue

????直接上代码，不解释原理。

//#include "LinkNode.h"

/**
* 链式队列
*/
template <typename T>
class LinkedQueue{
public:
	//inner class
	template <typename T>
	class LinkNode{
	public:
		//setter
		void setData(T data){
			this->data=data;
		}
		void setNext(LinkNode* next){
			this->next=next;
		}
		//getter
		T getData(){
			return this->data;
		}
		LinkNode<T>* getNext(){
			return this->next;
		}
		//constructor
		LinkNode(){
			this->setData(0);
			this->setNext(NULL);
		}
		LinkNode(T data,LinkNode* next){
			this->setData(0);
			this->setNext(NULL);
		}

	protected:

	private:
		T data;//数据域
		LinkNode* next;//指针域
	};

	//setter
	//getter
	//constructor
	LinkedQueue(){
		this->front=new LinkNode<T>;
		this->rear=this->front;
	}

	/**
	* 判断队空
	*/
	bool isEmpty(){
		return this->front==this->rear?true:false;
	}

	/**
	* 进队-[尾插法-后进后出]
	*/
	void enQueue(T e){
		LinkNode<T>* newNode=new LinkNode<T>;//创建新节点
		newNode->setData(e);
		//入队-尾插法
		this->rear->setNext(newNode);
		this->rear=newNode;
	}

	/**
	* 出队-[头删法-先进先出]
	*/
	void deQueue(T& e){
		LinkNode<T>* node=NULL;//辅助指针-记录出队结点
		//判断是否队空
		if (this->isEmpty()) return;
		//获取出队结点
		node=this->front->getNext();
		e=node->getData();
		//出队
		this->front->setNext(node->getNext());
		if (this->rear==node)
		{
			this->front=this->rear;
		}
		//释放结点
		delete node;
	}


protected:

private:
	LinkNode<T>* front;//队头
	LinkNode<T>* rear;//队尾
};

3 二叉树的链式存储结构实现

????这部分也是直接上代码，不解释原理。

3.1 树的结点定义-TreeNode


//定义节点
template <typename T>
class TreeNode{
public:
	//setter
	void setData(T data){
		if (typeid(data)==typeid(char))
		{
			this->data=data;
			return;
		}
		std::cout<<"The Type is Wrong!"<<std::endl;
	}
	void setLchild(TreeNode* lchild){
		if (lchild!=NULL)
		{
			this->lchild=lchild;
			return;
		}
		this->lchild=NULL;
	}
	void setRchild(TreeNode* rchild){
		if (rchild!=NULL)
		{
			this->rchild=rchild;
			return;
		}
		this->rchild=NULL;
	}
	//getter
	T getData(){
		return this->data;
	}
	TreeNode* getLchild(){
		return this->lchild;
	}
	TreeNode* getRchild(){
		return this->rchild;
	}
	//constructor
	TreeNode(){
		this->setData(0);
		this->lchild=NULL;
		this->rchild=NULL;
	}
	TreeNode(T data){
		this->setData(data);
		this->lchild=NULL;
		this->rchild=NULL;
	}
	//methods
 	virtual void visit(){
		std::cout<<" "<<this->data<<" "<<std::endl;
	}

	//前序遍历
	void preOrder(){
		this->visit();
		if (this->lchild!=NULL)
		{
			this->lchild->preOrder();
		}
		if (this->rchild!=NULL)
		{
			this->rchild->preOrder();
		}
	}

	//中序遍历
	void inOrder(){
		if (this->lchild!=NULL)
		{
			this->lchild->inOrder();
		}
		this->visit();
		if (this->rchild!=NULL)
		{
			this->rchild->inOrder();
		}
	}

	//后序遍历
	void postOrder(){
		if (this->lchild!=NULL)
		{
			this->lchild->postOrder();
		}
		if (this->rchild!=NULL)
		{
			this->rchild->postOrder();
		}
		this->visit();
	}
protected:

private:
	T data;//数据域
	TreeNode* lchild;//左孩子结点
	TreeNode* rchild;//右孩子结点
};

3.2 二叉树定义

#include "TreeNode.h"
#include "LinkedStack.h"
#include "LinkedQueue.h"

//定义二叉树
template <typename T>
class BinaryTree{
public:
	//setter
	void setRoot(TreeNode<T>* root){
		if (root!=NULL)
		{
			this->root=root;
			return;
		}
		this->root=NULL;
	}
	//getter
	TreeNode<T>* getRoot(){
		return this->root;
	}
	
protected:

private:
	TreeNode<T>* root;//根结点
};

3.3 前中后序遍历-递归算法实现

????直接放在binaryTree.h头文件中，作为BinaryTree类的成员方法即可。

//前序遍历
	void preOrder(){
		if (this->root!=NULL)
		{
			this->root->preOrder();
		}
	}
	//中序遍历
	void inOrder(){
		if (this->root!=NULL)
		{
			this->root->inOrder();
		}
	}
	//后序遍历
	void postOrder(){
		if (this->root!=NULL)
		{
			this->root->postOrder();
		}
	}

3.4 前中后序遍历-非递归算法实现

????直接放在binaryTree.h头文件中，作为BinaryTree类的成员方法即可。


	/**
	* 前序遍历非递归实现
	*/
	void preOrderWithStack(){
		LinkedStack<TreeNode<T>*> *S=new LinkedStack<TreeNode<T>*>;//初始化栈
		TreeNode<T>* p=this->root;//辅助指针
		if (S==NULL) return;
		//循环-前序遍历实现
		while (p!=NULL||!S->isEmpty())
		{
			if (p!=NULL)
			{
				p->visit();//访问根节点
				S->PushLinkedStack(p);//入栈-[记录根节点]
				p=p->getLchild();//左子树
			}else
			{
				S->PopLinkedStack(p);//出栈-[获取根节点]
				p=p->getRchild();//右子树
			}
		}
		//释放栈
		if (S!=NULL)
		{
			delete S;
		}
	}

	/**
	* 中序遍历非递归实现
	*/
	void inOrderWithStack(){
		LinkedStack<TreeNode<T>*>* S=new LinkedStack<TreeNode<T>*>;//初始化栈
		TreeNode<T>* p=this->root;//辅助指针
		if (S==NULL)
		{
			return;
		}
		//循环-中序遍历实现
		while (p!=NULL||!S->isEmpty())
		{
			if (p!=NULL)//p为根节点
			{
				S->PushLinkedStack(p);
				p=p->getLchild();
			}else
			{
				S->PopLinkedStack(p);
				p->visit();//访问当前节点
				p=p->getRchild();
			}
		}
		//释放栈
		if (S!=NULL)
		{
			delete S;
		}
		//TreeNode<char>* A=new TreeNode<char>;
		//A->setData('A');
		//S->PushLinkedStack(A);
		//LinkNode<TreeNode<T>*>* fNode=S->getHeader()->getNext();
		//std::cout<<S->getHeader()->getNext()<<"data:"<<fNode->getData()->getData()<<std::endl;
	}

	/**
	* 后序遍历非递归实现
	*/
	void postOrderWithStack(){
		LinkedStack<TreeNode<T>*>* S=new LinkedStack<TreeNode<T>*>;//初始化栈
		TreeNode<T>* p=this->root; //工作指针
		TreeNode<T>* r=NULL;//记录当前节点是否被访问过
		if (S==NULL) return;
		//循环-后序遍历实现
		while (p!=NULL||!S->isEmpty())
		{
			if (p!=NULL)
			{
				S->PushLinkedStack(p);//子树根节点/左子树入栈
				p=p->getLchild();//继续查找左子树
			}else
			{
				p=S->getTop()->getData();//获取栈顶元素
				//如果右子树不为空
				if (p->getRchild()!=NULL&&r!=p->getRchild())
				{
					p=p->getRchild();//继续查找右子树
				}else
				{
					//右子树为空-访问左子树
					S->PopLinkedStack(p);//出栈-获取左子树/根节点
					p->visit();//访问左子树/根节点
					r=p;//记录当前被访问的结点
					p=NULL;//将工作指针置空
				}//if
			}//else
		}//while
		//释放栈
		if (S!=NULL) delete S;
	}

3.5 层序遍历算法实现

????直接放在binaryTree.h头文件中，作为BinaryTree类的成员方法即可。

	/**
	* 层次遍历
	*/
	void levelOrder(){
		if (this->root!=NULL)
		{
			LinkedQueue<TreeNode<T>*>* Q=new LinkedQueue<TreeNode<T>*>;//初始化队列
			TreeNode<T>* p=this->root;//工作指针
			if (Q==NULL) return;
			Q->enQueue(p);//根节点入队
			//循环-层次遍历
			while (!Q->isEmpty())
			{
				Q->deQueue(p);//首个结点出队
				p->visit();//访问结点
				if (p->getLchild()!=NULL)//左子树不为空-左子树入队
					Q->enQueue(p->getLchild());
				if (p->getRchild()!=NULL)//右子树不为空-右子树入队
					Q->enQueue(p->getRchild());
			}//while
			//释放队列
			if (Q!=NULL) delete Q;
		}
	}

4 代码测试

????此处手动创建二叉树结点，并设置树结点之间的关系，二叉树的结构如下图，
二叉树结构图
????测试代码如下，

#include "BinaryTree.h"
void test_binaryTree(){
	//创建结点
	TreeNode<char>* A=new TreeNode<char>('A');
	TreeNode<char>* B=new TreeNode<char>('B');
	TreeNode<char>* C=new TreeNode<char>('C');
	TreeNode<char>* D=new TreeNode<char>('D');
	TreeNode<char>* E=new TreeNode<char>('E');
	TreeNode<char>* F=new TreeNode<char>('F');
	TreeNode<char>* G=new TreeNode<char>('G');
	TreeNode<char>* H=new TreeNode<char>('H');
	TreeNode<char>* I=new TreeNode<char>('I');
	//设置结点间的关系
	H->setRchild(I);
	C->setRchild(D);
	G->setLchild(H);
	B->setRchild(C);
	E->setLchild(F);
	E->setRchild(G);
	A->setLchild(B);
	A->setRchild(E);
	//创建二叉树
	BinaryTree<char>* bTree=new BinaryTree<char>;
	bTree->setRoot(A);
	//bTree->preOrder();//前序遍历
	//bTree->inOrder();//中序遍历
	//bTree->postOrder();//后序遍历
	bTree->levelOrder();//层序遍历
	//bTree->inOrderWithStack();//中序遍历非递归实现
	//bTree->preOrderWithStack();//前序遍历非递归实现
	//bTree->postOrderWithStack();//后序遍历非递归实现
}




int main(int argc,char** argv){
	test_binaryTree();
	return 0;
}