二叉木遍歴の非再帰的実現

二叉木遍歴の非再帰的実現
二叉木遍歴アルゴリズムの重要性はみんな知っていて、多くのアルゴリズムの基礎で、その再帰の実現はとても簡単で、データ構造を学んだ学生はすべて簡単に書くことができると信じています.ツリーの前順ループ、中順ループ、および後続ループの非再帰的実装を書く必要がある場合は、時間がかかる場合があります.次に私の実現方法を示します.
前の順序:
二叉木の前序非再帰実装は、間違いなく、補助空間としてスタックが必要であり、まずルートノードをスタックに入れ、スタックが空でない場合、スタックトップ要素を取り出し、その要素にアクセスし、右の子供をスタックに入れ、左の子供をスタックに入れる.このようにずっと進むと,スタックが空であることが分かり,得られたアクセスシーケンスが二叉木の先根遍歴シーケンスである.
実装コードを次に示します.
ツリーのノード構造:

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

ルートループコード:

//       
class Solution1 {
public:
	vector preorderTraversal1(TreeNode *root) {
		vector ret ;
		if (root == NULL)
			return ret ;
		stack s ;
		s.push(root) ;
		TreeNode* tmpNode = NULL ;
		while(!s.empty())
		{
			tmpNode = s.top() ;
			s.pop() ;
			ret.push_back(tmpNode->val) ;

			if (tmpNode->right != NULL)
				s.push(tmpNode->right) ;
			if (tmpNode->left!= NULL)
				s.push(tmpNode->left) ;
		}
		return ret ;
	}

	vector preorderTraversal2(TreeNode *root) {
		vector ret ;
		stack s ;
		while(root != NULL || !s.empty())
		{
			if (root != NULL)
			{
				ret.push_back(root->val) ;
				s.push(root) ;
				root = root->left ;
			}
			else
			{
				root = s.top() ; //  
				s.pop() ;
				root = root->right ;
			}
		}

		return ret ;
	}
};

ここでは2つの実装方式を示し,preorderTraversal 1()は上記の考え方に厳格に従って実装される.preorderTraversal 2()の考え方は少し異なり、まずノードにアクセスしてスタックに入れ、それから左ノードにアクセスし続け、現在のノードに左ノードの位置がないことを知り、このとき遡及して、前のノードの右子供ノードにアクセスします.このままでは,現在のノードが空であり,スタックも空であることが分かる.このとき,アクセスシーケンスは同様に二叉木の前シーケンス遍歴シーケンスである.
中間パス:
中序遍歴の思想は上の前序遍歴の第2の実現と一致し、アクセスのタイミングが異なるだけで、以下は直接実現コードを与える.

//       
class Solution2
{
public:
	vector inorderTraversla(TreeNode *root)
	{
		vector ret ;
		stack s ;
		while (root != NULL || !s.empty())
		{
			if (root != NULL)
			{
				s.push(root) ;
				root = root->left ;
			}
			else
			{
				//    
				root = s.top() ;
				s.pop() ;
				ret.push_back(root->val) ; //  
				root = root->right ;
			}
		}
		return ret ;
	}
};

次のパス:
後続のループの非再帰的実装は、ツリーの非再帰的ループアルゴリズムの中で最も複雑なものであり、ツリーのノードデータ構造にデータ項目を追加することでアクセスの状態を記録し、右サブツリーがアクセスされたかどうかをマークすることで実現することができるが、ツリーのデータ構造を変更する必要がある.
ここで、私たちは考え方を変えて、問題を転化することができて、私たちはまず数の後続の遍歴の逆序を求めることができて、このように問題は迎刃して解くことができます.
このような順序でノードにアクセスし、得られたアクセスシーケンスを逆順序にすることができ、得られた新しいシーケンスはツリーの後続の遍歴シーケンスであり、アクセスシーケンスの実現については、上記のルート遍歴と一致する方法であり、ここでは後述しない.次に、コードを直接示します.

//       
class Solution3 {
public:
    vector postorderTraversal(TreeNode *root) {
        //           ret ，
		//   ret  ，          
		vector ret ; 
		if (root == NULL) return ret ;
		stack s ;
		s.push(root) ;
		TreeNode* tmpNode = NULL ;
		while(!s.empty())
		{
			tmpNode = s.top() ;
			s.pop() ;
			ret.push_back(tmpNode->val) ; //     
			if (tmpNode->left != NULL)//       
				s.push(tmpNode->left) ;
			if (tmpNode->right != NULL)//       
				s.push(tmpNode->right) ;
		}
		reverse(ret.begin(), ret.end()) ;

		return ret ;
    }
};

OK、上の3つの遍歴アルゴリズムのテストプログラムを以下に示します.

#include 
#include 
#include 
#include 
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//       
class Solution1 {
public:
	vector preorderTraversal1(TreeNode *root) {
		vector ret ;
		if (root == NULL)
			return ret ;
		stack s ;
		s.push(root) ;
		TreeNode* tmpNode = NULL ;
		while(!s.empty())
		{
			tmpNode = s.top() ;
			s.pop() ;
			ret.push_back(tmpNode->val) ;

			if (tmpNode->right != NULL)
				s.push(tmpNode->right) ;
			if (tmpNode->left!= NULL)
				s.push(tmpNode->left) ;
		}
		return ret ;
	}

	vector preorderTraversal2(TreeNode *root) {
		vector ret ;
		stack s ;
		while(root != NULL || !s.empty())
		{
			if (root != NULL)
			{
				ret.push_back(root->val) ;
				s.push(root) ;
				root = root->left ;
			}
			else
			{
				root = s.top() ; //  
				s.pop() ;
				root = root->right ;
			}
		}

		return ret ;
	}
};

//       
class Solution2
{
public:
	vector inorderTraversla(TreeNode *root)
	{
		vector ret ;
		stack s ;
		while (root != NULL || !s.empty())
		{
			if (root != NULL)
			{
				s.push(root) ;
				root = root->left ;
			}
			else
			{
				//    
				root = s.top() ;
				s.pop() ;
				ret.push_back(root->val) ; //  
				root = root->right ;
			}
		}
		return ret ;
	}
};


//       
class Solution3 {
public:
    vector postorderTraversal(TreeNode *root) {
        //           ret ，
		//   ret  ，          
		vector ret ; 
		if (root == NULL) return ret ;
		stack s ;
		s.push(root) ;
		TreeNode* tmpNode = NULL ;
		while(!s.empty())
		{
			tmpNode = s.top() ;
			s.pop() ;
			ret.push_back(tmpNode->val) ; //     
			if (tmpNode->left != NULL)//       
				s.push(tmpNode->left) ;
			if (tmpNode->right != NULL)//       
				s.push(tmpNode->right) ;
		}
		reverse(ret.begin(), ret.end()) ;

		return ret ;
    }
};

int main(int argc, char **argv)
{
	/*************************************************************
	*   :             1
	*                  /   \
	*                 2     3
	*                /  \    \
	*               4    5    6
	*************************************************************/
	TreeNode* root = new TreeNode(1) ;
	root->left = new TreeNode(2) ;
	root->right = new TreeNode(3) ;
	root->left->left = new TreeNode(4) ;
	root->left->right = new TreeNode(5) ;
	root->right->right = new TreeNode(6) ;

	//    
	Solution1 s1;
	vector ret1 = s1.preorderTraversal1(root) ;
	cout << "       ：" << endl;
	for (int i = 0; i < ret1.size(); ++ i)
		cout << ret1[i] << " " ;
	cout << endl;

	//    
	Solution2 s2;
	vector ret2 = s2.inorderTraversla(root) ;
	cout << "       ：" << endl;
	for (int i = 0; i < ret2.size(); ++ i)
		cout << ret2[i] << " " ;
	cout << endl;

	//    
	Solution3 s3;
	vector ret3 = s3.postorderTraversal(root) ;
	cout << "       ：" << endl;
	for (int i = 0; i < ret3.size(); ++ i)
		cout << ret3[i] << " " ;
	cout << endl;

	return 0 ;
}