二叉樹，遞歸非遞歸遍歷算法（全）

二叉樹，遞歸非遞歸遍歷算法（全）

包含了所有的非遞歸和遞歸的算法：

#include  
#include  
#include  
using namespace std;  

//二叉樹結點的描述  
typedef struct BiTNode  
{  
	char data;  
	struct BiTNode *lchild, *rchild;      //左右孩子  
}BiTNode,*BiTree;  

//按先序遍歷創建二叉樹  
//BiTree *CreateBiTree()     //返回結點指針類型  
//void CreateBiTree(BiTree &root)      //引用類型的參數  
void CreateBiTree(BiTNode **root)    //二級指針作為函數參數  
{  
	char ch; //要插入的數據  
	scanf("\n%c", &ch);  
	//cin>>ch;  
	if(ch=='#')  
		*root = NULL;  
	else  
	{  
		*root = (BiTNode *)malloc(sizeof(BiTNode));  
		(*root)->data = ch;  
		printf("請輸入%c的左孩子：",ch);  
		CreateBiTree(&((*root)->lchild));  
		printf("請輸入%c的右孩子：",ch);  
		CreateBiTree(&((*root)->rchild));  
	}  
}  

//前序遍歷的算法程序  
void PreOrder(BiTNode *root)  
{  
	if(root==NULL)  
		return ;  
	printf("%c ", root->data); //輸出數據  
	PreOrder(root->lchild); //遞歸調用，前序遍歷左子樹  
	PreOrder(root->rchild); //遞歸調用，前序遍歷右子樹  
}  

//中序遍歷的算法程序  
void InOrder(BiTNode *root)  
{  
	if(root==NULL)  
		return ;  
	InOrder(root->lchild); //遞歸調用，前序遍歷左子樹  
	printf("%c ", root->data); //輸出數據  
	InOrder(root->rchild); //遞歸調用，前序遍歷右子樹  
}  

//後序遍歷的算法程序  
void PostOrder(BiTNode *root)  
{  
	if(root==NULL)  
		return ;  
	PostOrder(root->lchild);      //遞歸調用，前序遍歷左子樹  
	PostOrder(root->rchild);      //遞歸調用，前序遍歷右子樹  
	printf("%c ", root->data);    //輸出數據    
}  

/* 
二叉樹的非遞歸前序遍歷，前序遍歷思想：先讓根進棧，只要棧不為空，就可以做彈出操作， 
每次彈出一個結點，記得把它的左右結點都進棧，記得右子樹先進棧，這樣可以保證右子樹在棧中總處於左子樹的下面。 
*/  
void PreOrder_Nonrecursive2(BiTree T)     //先序遍歷的非遞歸    
{  
	if(!T)    
		return ;    

	stack s;  
	s.push(T);  //<首先將根節點壓入

	while(!s.empty())  
	{  
		BiTree temp = s.top();  
		cout<data<<" ";  
		s.pop();  //<輸出最上方節點，同時彈出
		if(temp->rchild)  
			s.push(temp->rchild);  //<壓入右節點  
		if(temp->lchild)  
			s.push(temp->lchild);   //<壓入左節點
	}  
}  


void PreOrder_Nonrecursive(BiTree T)     //先序遍歷的非遞歸  
{  
	if(!T)  
		return ;  

	stack s;  
	while(T)          // 左子樹上的節點全部壓入到棧中  
	{  
		s.push(T);  
		cout<data<<"  ";  
		T = T->lchild;  
	}  

	while(!s.empty())  
	{          
		BiTree temp = s.top()->rchild;  // 獲得棧頂元素的右子樹
		s.pop();                        // 彈出棧頂元素  
		while(temp)          // 棧頂元素存在右子樹，則對右子樹同樣遍歷到最下方  
		{  
			s.push(temp);  
			cout<data<<"  ";  //<前序遍歷，在壓入節點的時候就需要輸出，表示根節點
			temp = temp->lchild;  
		}  
	}  
}  

void InOrderTraverse(BiTree T)   // 中序遍歷的非遞歸  
{  
	if(!T)  
		return ;  
	stack S;  
	BiTree curr = T->lchild;    //< 指向當前要檢查的節點  
	S.push(T);  //<先將根節點壓入
	while(curr || !S.empty())  
	{  
		while(curr)    //<一直找到對應的左節點最深處
		{  
			S.push(curr);  
			curr = curr->lchild;  
		}  
		curr = S.top();  //<彈出棧頂，對應左孩子
		S.pop();  
		cout<data<<"  "; //<中序遍歷，在壓入節點之後，輸出左孩子  
		curr = curr->rchild;  //<調用右孩子，繼續操作
	}  
}  

void PostOrder_Nonrecursive(BiTree T)  // 後序遍歷的非遞歸    
{    
	stack S;    
	BiTree curr = T ;           // 指向當前要檢查的節點  
	BiTree previsited = NULL;    // 指向前一個被訪問的節點  
	while(curr || !S.empty())  // 棧空時結束    
	{    
		while(curr)            // 一直向左走直到為空  
		{    
			S.push(curr);    
			curr = curr->lchild;    
		}    
		curr = S.top();  
		// 當前節點的右孩子如果為空或者已經被訪問，則訪問當前節點  
		if(curr->rchild == NULL || curr->rchild == previsited)    
		{    
			cout<data<<"  ";    
			previsited = curr;    
			S.pop();    
			curr = NULL;    
		}    
		else  
			curr = curr->rchild;      // 否則訪問右孩子  
	}    
}   

void PostOrder_Nonrecursive2(BiTree T)  // 後序遍歷的非遞歸     雙棧法  
{    
	stack s1 , s2;    
	BiTree curr ;           // 指向當前要檢查的節點  
	s1.push(T);  
	while(!s1.empty())  // 棧空時結束    
	{  
		curr = s1.top();  
		s1.pop();  
		s2.push(curr);  
		if(curr->lchild)  
			s1.push(curr->lchild);  
		if(curr->rchild)  
			s1.push(curr->rchild);  
	}  
	while(!s2.empty())  
	{  
		printf("%c ", s2.top()->data);  
		s2.pop();  
	}  
}  


int visit(BiTree T)  
{  
	if(T)  
	{  
		printf("%c ",T->data);  
		return 1;  
	}  
	else  
		return 0;  
}  

void LeverTraverse(BiTree T)   //方法一、非遞歸層次遍歷二叉樹   
{  
	queue  Q;  
	BiTree p;  
	p = T;  
	if(visit(p)==1)  
		Q.push(p);  
	while(!Q.empty())  
	{  
		p = Q.front();  
		Q.pop();  
		if(visit(p->lchild) == 1)   
			Q.push(p->lchild);  
		if(visit(p->rchild) == 1)  
			Q.push(p->rchild);  
	}  
}  
void LevelOrder(BiTree BT)     //方法二、非遞歸層次遍歷二叉樹   
{  
	BiTNode *queue[10];//定義隊列有十個空間  
	if (BT==NULL)  
		return;  
	int front,rear;  
	front=rear=0;  
	queue[rear++]=BT;  
	while(front!=rear)//如果隊尾指針不等於對頭指針時  
	{  
		cout<data<<"  ";  //輸出遍歷結果  
		if(queue[front]->lchild!=NULL)  //將隊首結點的左孩子指針入隊列  
		{  
			queue[rear]=queue[front]->lchild;  
			rear++;    //隊尾指針後移一位  
		}  
		if(queue[front]->rchild!=NULL)  
		{  
			queue[rear]=queue[front]->rchild;    //將隊首結點的右孩子指針入隊列  
			rear++;   //隊尾指針後移一位  
		}  
		front++;    //對頭指針後移一位  
	}  
}  

int depth(BiTNode *T)   //樹的深度  
{  
	if(!T)  
		return 0;  
	int d1,d2;  
	d1=depth(T->lchild);  
	d2=depth(T->rchild);  
	return (d1>d2?d1:d2)+1;  
	//return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;  
}  
int CountNode(BiTNode *T)  
{  
	if(T == NULL)  
		return 0;  
	return 1+CountNode(T->lchild)+CountNode(T->rchild);  
}  

int main(void)  
{  
	BiTNode *root=NULL; //定義一個根結點  
	int flag=1,k;  
	printf("                     本程序實現二叉樹的基本操作。\n");  
	printf("可以進行建立二叉樹，遞歸先序、中序、後序遍歷，非遞歸先序、中序遍歷及非遞歸層序遍歷等操作。\n");  
	printf("請建立二叉樹並輸入二叉樹的根節點：");  
	CreateBiTree(&root); 
	if(root)  
	{  
		printf("遞歸先序遍歷二叉樹的結果為：");  
		PreOrder(root);  
		printf("\n");  
		printf("遞歸中序遍歷二叉樹的結果為：");  
		InOrder(root);  
		printf("\n");  
		printf("遞歸後序遍歷二叉樹的結果為：");  
		PostOrder(root);  
		printf("\n");  
		printf("非遞歸先序遍歷二叉樹：");  
		PreOrder_Nonrecursive(root);  
		printf("\n");  
		printf("非遞歸中序遍歷二叉樹：");  
		InOrderTraverse(root);  
		printf("\n");  
		printf("非遞歸後序遍歷二叉樹：");  
		PostOrder_Nonrecursive(root);  
		printf("\n");  
		printf("非遞歸層序遍歷二叉樹：");  
		//LeverTraverse(root);  
		LevelOrder(root);  
		printf("\n");  
		printf("這棵二叉樹的深度為：%d\n",depth(root));  
		printf("這棵二叉樹的結點個數為：%d\n",CountNode(root));  
		printf("程序運行結束，按任意鍵退出！\n");  
	}  
	system("pause");  
	return 0;  
}