二叉木の三種類の遍歴方式:再帰、スタック、循環分類:C/C+...

3つの方法のうち,再帰が最も簡単で,スタックに次いでループが最も面倒である.再帰的な深さが大きすぎるとスタックがオーバーフローします.スタックの方式には追加の補助空間が必要です.ループプログラミングが一番面倒です.
まず、再帰です.

//    
void midPrint_r(TreeNode* root)
{//    
	if(root==NULL)
		return;
	if(root->left)
		midPrint_r(root->left);
	cout<val<right)
		midPrint_r(root->right);
}

void prePrint_r(TreeNode* root)
{//    
	if(root==NULL)
		return;
	cout<val<left)
		prePrint_r(root->left);	
	if(root->right)
		prePrint_r(root->right);
}

void postPrint_r(TreeNode* root)
{//    
	if(root==NULL)
		return;
	if(root->left)
		postPrint_r(root->left);	
	if(root->right)
		postPrint_r(root->right);
	cout<val<

スタック方法:まずループしてノードをスタックに押し込み、それから1つずつポップアップします.

//      
void midPrint_l(TreeNode* root)
{
	stack s;
	TreeNode *cur = root;
	while(!s.empty() || cur != NULL)
	{
		while(cur != NULL)
		{
			s.push(cur);
			cur = cur->left;
		}
		cur = s.top();
		s.pop();
		cout<val<right;
	}
}

void prePrint_l(TreeNode* root)
{
	stack s;
	TreeNode *cur = root;
	while(!s.empty() || cur != NULL)
	{
		while(cur != NULL)
		{
			cout<var<left;
		}
		cur = s.top();
		s.pop();
		cur = cur->right;
	}
}

void postPrint_l(TreeNode* root)
{
	//the original method
	/*
	We use a prev variable to keep track of the previously-traversed node.
	Let’s assume curr is the current node that’s on top of the stack. When
	prev is curr‘s parent, we are traversing down the tree. In this case,
	we try to traverse to curr‘s left child if available (ie, push left
	child to the stack). If it is not available, we look at curr‘s right
	child. If both left and right child do not exist (ie, curr is a leaf node),
	we print curr‘s value and pop it off the stack.If prev is curr‘s left
	child, we are traversing up the tree from the left. We look at curr‘s
	right child. If it is available, then traverse down the right child (ie,
	push right child to the stack), otherwise print curr‘s value and pop it
	off the stack.If prev is curr‘s right child, we are traversing up the tree
	from the right. In this case, we print curr‘s value and pop it off the stack.
	*/
	if(root == NULL)
	{
		return;
	}
	stack s;
	s.push(root);
	TreeNode *cur = NULL;
	TreeNode *pre = NULL;
	while(!s.empty())
	{
		cur = s.top();
		//left down or right down
		if( pre == NULL || pre->left == cur || pre->right == cur)
		{//        ，        ，
		//          ，       
			if(cur->left != NULL)
			{//     ，           
				s.push(cur->left);
			}
			else if(cur->right != NULL)
			{
				s.push(cur->right);
			}
			else
			{//       
				cout<var<left == pre)
		{//      
			if(cur->right != NULL)
			{//          ，  ，  
				s.push(cur->right);
			}
			else
			{
				cout<var<right == pre)
		{//     ,         ，       
			cout<var< s;
	s.push(root);
	TreeNode *cur = NULL;
	TreeNode *pre = NULL;
	while(!s.empty())
	{
	    cur = s.top();
	    if(pre == NULL || pre->left == cur || pre->right == cur)
		{
	        if(cur->left != NULL)
			{
	            s.push(cur->left);
	        }
	        else if(cur->right != NULL)
			{
	            s.push(cur->right);
	        }
	    }
	    else if(cur->left == pre)
		{
	        if(cur->right != NULL)
			{
	            s.push(cur->right);
	        }
	    }
	    else
		{
	        cout<var<

循環:葉の結点の左右のポインタが空の特徴を利用して、葉の結点に直接の後継を設置して、この子の結点を出力した後、更にその直接の後継に戻ります;

//         
void midPrint_m(TreeNode *root)
{
	TreeNode *cur = root;
	TreeNode *pre = NULL;
	while(cur != NULL)
	{
		if(cur->left == NULL)
		{//     ，     
			cout<var<right;
		}
		else
		{
			pre = cur->left;
			while( pre->right != NULL && pre->right != cur )
			{//  cur     
				pre = pre->right;
			}
			if(pre->right == NULL)
			{//      
				pre->right = cur;
				cur = cur->left;
			}
			else
			{
				pre->right = NULL;//      
				cout<var<right;
			}
		}
	}
}

void prePrint_m(TreeNode *root)
{//       
	TreeNode *cur = root;
	TreeNode *pre = NULL;
	while(cur != NULL)
	{
		if(cur->left == NULL)
		{
			cout<var<right;
		}
		else
		{
			pre = cur->left;
			while( pre->right != NULL && pre->right != cur )
			{
				pre = pre->right;
			}
			if(pre->right == NULL)
			{
				pre->right = cur;
				cout<var<left;
			}
			else
			{
				pre->right = NULL;
				cur = cur->right;
			}
		}
	}
}
//this is the most difficult algorithm
void reverse_out(TreeNode *from,TreeNode *to)
{
	//first reverse from->to
	//reverse
	TreeNode *cur = from;
	TreeNode *post = cur->right;
	while(cur != to)
	{
		TreeNode *tmp = post->right;
		post->right = cur;
		cur = post;
		post = tmp;
	}
	//already reverse,output list
	TreeNode *traversal = cur;
	while( cur != from )
	{
		cout<var<right;
	}
	cout<var<right;
	while(cur != from)
	{
		TreeNode *tmp = post->right;
		post->right = cur;
		cur = post;
		post = tmp;
	}
	//restore to's right
	to->right = NULL;
}
void postPrint_m(TreeNode *root)
{
	TreeNode *newroot = new TreeNode(0);
	newroot->left = root;
	newroot->right = NULL;
	TreeNode *cur = newroot;
	TreeNode *pre = NULL;
	while(cur != NULL)
	{
		if(cur->left == NULL)
		{
			cur = cur->right;
		}
		else
		{
			pre = cur->left;
			while(pre->right != NULL && pre->right != cur)
			{
				pre = pre->right;
			}
			if(pre->right == NULL)
			{
				pre->right = cur;
				cur = cur->left;
			}
			else
			{
				pre->right = NULL;
				reverse_out(cur->left,pre);
				cur = cur->right;
			}
		}
	}
}

前シーケンス、中シーケンスのプログラミングは比較的簡単で、後シーケンスに触れると面倒になることがわかります.
転載先:https://www.cnblogs.com/zclzqbx/p/4687103.html