二叉樹非遞歸前序,中序,後序周遊,層序周遊,之字周遊

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

struct TreeNode{
	char val;
	TreeNode* left,*right;
	TreeNode(char v):val(v),left(NULL),right(NULL){}
};

/*按照中序周遊方式建立二叉樹*/
void createTree(TreeNode*& root)
{
	char c;
	cin>>c;
	if (c=='#'){
		root=NULL;
	}else{
		root=new TreeNode(c);
		createTree(root->left);
		createTree(root->right);
	}
}


//遞歸前序
void preTravel(TreeNode* root)
{
	if (!root)	return;
	cout<<root->val<<" ";
	preTravel(root->left);
	preTravel(root->right);
}
//遞歸中序
void midTravel(TreeNode* root)
{
	if (!root)	return;
	midTravel(root->left);
	cout<<root->val<<" ";
	midTravel(root->right);
}
//遞歸後序
void tailTravel(TreeNode* root)
{
	if (!root)	return;
	tailTravel(root->left);
	tailTravel(root->right);
	cout<<root->val<<" ";
}

//非遞歸前序:深度優先算法dfs
void preTravel_un(TreeNode* root)
{
	if (!root)	return;
	stack<TreeNode*> s;
	s.push(root);
	while(!s.empty()){
		TreeNode* node = s.top();
		s.pop();
		cout<<node->val<<" ";
		if(node->right) s.push(node->right);
		if(node->left)  s.push(node->left);
	}
}
//非遞歸中序
void midTravel_un(TreeNode* root)
{
	if (!root)	return;
	stack<TreeNode*> s;
	while(!s.empty() || root){
		//一直周遊到左子樹的最下邊，并将沿途的節點如入棧
		while(root){
			s.push(root);
			root=root->left;
		}
		//root為空：說明已經到達左子樹的最下邊，開始出棧，現在出棧的是“根”
		if (!s.empty()){
			root=s.top();
			s.pop();
			cout<<root->val<<" ";
			//進入“根”的右子樹，開始在新節點下查找左子樹的最下邊，這是遞歸的自我實作
			root=root->right;
		}
	}
}
//非遞歸後序
void tailTravel_un(TreeNode* root)
{
	if (!root)	return;
	stack<TreeNode*> s;
	//cur目前準備通路的節點，右子樹被通路過了，或者為空，就通路cur
	//pre記錄上次通路的節點，判斷目前根節點的右子樹是否被通路過
	TreeNode *pre=NULL,*cur=NULL;
	s.push(root);
	while(!s.empty()){
		cur = s.top();	
		/*
			目前為葉節點,
			目前結點右子樹為空: pre==cur->left
		    存在右子樹:	    pre==cur->right	
		    因為這裡本身就是按照"中右左"的順序入棧,出棧剛好就是"左右中"
		*/
		if ((!cur->left && !cur->right) || (pre!=NULL && (pre==cur->left||pre==cur->right))){
			cout<<cur->val<<" ";
			s.pop();
			pre=cur;
		}else{
			if (cur->right)		s.push(cur->right);
			if (cur->left)		s.push(cur->left);
		}
	}
}

/*層序周遊:廣度優先dfs*/
void levelTravel(TreeNode* root)
{
	if (!root)	return;
	queue<TreeNode*> q;
	q.push(root);
	while(!q.empty()){
		TreeNode* node = q.front();
		q.pop();
		cout<<node->val<<" ";
		if (node->left)		q.push(node->left);
		if (node->right)	q.push(node->right);
	}
}

/*之字形周遊*/
void zigzag(TreeNode* root)
{
	if (!root)	return;
	vector<vector<char>> res;
	queue<TreeNode*>	q;	//存儲目前層已經排序的節點
	stack<TreeNode*>	s;	//暫存某一層的節點,排序後放入q
	q.push(root);			
	bool isLeft=true;		//從左往右輸出
	while(!q.empty()){
		vector<char> memo;
		int n=q.size();	//代表目前一層的節點個數
		int i=0;
		while(i<n){
			TreeNode* node=q.front();
			memo.push_back(node->val);
			q.pop();
			if (isLeft){
				if (node->left)		s.push(node->left);
				if (node->right)	s.push(node->right);
			}else{
				if (node->right)	s.push(node->right);
				if (node->left)		s.push(node->left);
			}
			i++;
		}
		while(!s.empty()){
			q.push(s.top());
			s.pop();
		}
		res.push_back(memo);
		isLeft=isLeft?false:true;
	}
	for(auto&v:res){
		for(auto&c:v){
			cout<<c<<" ";
		}
		cout<<endl;
	}
}

//前序周遊的順序建立ab#ef##m##c#gh##i##
int main()
{
	TreeNode* root=NULL;
	createTree(root);
	cout<<"建立 ok"<<endl;

	preTravel(root);
	cout<<endl;
	preTravel_un(root);
	cout<<endl<<"前序 ok"<<endl;
	midTravel(root);
	cout<<endl;
	midTravel_un(root);
	cout<<endl<<"中序 ok"<<endl;
	tailTravel(root);
	cout<<endl;
	tailTravel_un(root);
	cout<<endl<<"後序 ok"<<endl;
	levelTravel(root);
	cout<<endl<<"層序 ok"<<endl;
	zigzag(root);
	cout<<"之字 ok"<<endl;
	dfs(root);
}