程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 二叉樹,遞歸非遞歸遍歷算法(全)

二叉樹,遞歸非遞歸遍歷算法(全)

編輯:C++入門知識

二叉樹,遞歸非遞歸遍歷算法(全)


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

#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;  
}  


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved