再帰と非再帰は二叉木を遍歴する

10872 ワード

1ツリー接点
2先順にツリーを巡回
3中順にツリーを巡回
4後順にツリーを巡回
5試験サンプル
1ツリー接点
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
2先順にツリーを巡回
ツリーの再帰アルゴリズムは、次のように定義されます.
二叉木が空であれば、空操作;そうでない場合(1)ルートノードにアクセスします.(2)左サブツリーを順に遍歴する.(3)後順に右サブツリーを遍歴する.
コードは次のとおりです.
 
/*   */

void PreOrderTraverseTree(BinaryTreeNode *pRoot)

{

	if (pRoot != NULL)

	{

		cout << pRoot->m_nValue << " ";

		PreOrderTraverseTree(pRoot->m_pLeft);

		PreOrderTraverseTree(pRoot->m_pRight);

	}

}

二叉木を順次巡回する非再帰アルゴリズムは、次のように定義されます.
まずスタックstacknodesを作成し、まずルートノードをスタックに入れます.
次にwhileループ、すなわちwhile(!nodes.empty())に入り、ノードがポップアップされます.ノードの値を巡回し、ノードの右の子をスタックに入れ、ノードの左の子を再びスタックに入れます.
whileサイクルが終わるまで.
コードは次のとおりです.
 
/*   */

void PreOrderTraverseTreeNoRecursive(BinaryTreeNode *pRoot)

{

	if (pRoot == NULL)

	{

		return;

	}



	stack<BinaryTreeNode *> nodes;

	nodes.push(pRoot);

	while (!nodes.empty())

	{

		BinaryTreeNode *pNode = nodes.top();

		nodes.pop();

		cout << pNode->m_nValue << " ";



		if (pNode->m_pRight != NULL)

		{

			nodes.push(pNode->m_pRight);

		}

		if (pNode->m_pLeft != NULL)

		{

			nodes.push(pNode->m_pLeft);

		}

	}

}


3中順にツリーを巡回
 
中序遍歴二叉木の再帰アルゴリズムは以下の通りである.
二叉木が空であれば、空操作;そうでなければ(1)中序は左サブツリーを遍歴する.(2)ルートノードへのアクセス;(3)中順に右サブツリーを遍歴する.
コードは次のとおりです.
 
/*   */

void InOrderTraverseTree(BinaryTreeNode *pRoot)

{

	if (pRoot != NULL)

	{

		InOrderTraverseTree(pRoot->m_pLeft);

		cout << pRoot->m_nValue << " ";

		InOrderTraverseTree(pRoot->m_pRight);

	}

}

中序遍歴二叉木の非再帰アルゴリズムは以下の通りである.
 
 
/*   */

void InOrderTraverseTreeNoRecursive(BinaryTreeNode *pRoot)

{

	if (pRoot == NULL)

	{

		return;

	}



	stack<BinaryTreeNode *> nodes;

	BinaryTreeNode *pCurrent = pRoot;

	while (!nodes.empty() || pCurrent != NULL)

	{

		if (pCurrent != NULL)

		{

			nodes.push(pCurrent);

			pCurrent = pCurrent->m_pLeft;

		}

		else

		{

			pCurrent = nodes.top();

			nodes.pop();

			cout << pCurrent->m_nValue << " ";

			pCurrent = pCurrent->m_pRight;

		}

	}

}

4後順にツリーを巡回
 
後順に二叉木を巡る再帰アルゴリズムは以下の通りである.
二叉木が空であれば、空操作;そうでなければ(1)後順に左サブツリーを遍歴する.(2)後順に右サブツリーを遍歴する.(3)ルートノードへのアクセス;
 
/*   */

void PostOrderTraverseTree(BinaryTreeNode *pRoot)

{

	if (pRoot != NULL)

	{

		PostOrderTraverseTree(pRoot->m_pLeft);

		PostOrderTraverseTree(pRoot->m_pRight);

		cout << pRoot->m_nValue << " ";

	}

}

後順に二叉木を遍歴する非再帰アルゴリズムは以下の通りである.
 
 
/*   */

void PostOrderTraverseTreeNoRecursive(BinaryTreeNode *pRoot)

{

	if (pRoot == NULL)

	{

		return;

	}



	stack<BinaryTreeNode *> traverseNodes;

	stack<BinaryTreeNode *> nodes;

	traverseNodes.push(pRoot);

	while (!traverseNodes.empty())

	{

		BinaryTreeNode *pNode = traverseNodes.top();

		traverseNodes.pop();

		if (pNode->m_pLeft != NULL)

		{

			traverseNodes.push(pNode->m_pLeft);

		}

		if (pNode->m_pRight != NULL)

		{

			traverseNodes.push(pNode->m_pRight);

		}

		nodes.push(pNode);

	}



	while (!nodes.empty())

	{

		BinaryTreeNode *pNode = nodes.top();

		nodes.pop();

		cout << pNode->m_nValue << " ";

	}

}

 
5試験サンプル
ファイルh
 
struct BinaryTreeNode 

{

	int                    m_nValue; 

	BinaryTreeNode*        m_pLeft;  

	BinaryTreeNode*        m_pRight; 

};



BinaryTreeNode* CreateBinaryTreeNode(int value);

void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight);

void PrintTreeNode(BinaryTreeNode* pNode);

void PrintTree(BinaryTreeNode* pRoot);

void DestroyTree(BinaryTreeNode* pRoot);


ファイルcpp
 
 
#include "BinaryTree.h"

#include <cstdio>



BinaryTreeNode* CreateBinaryTreeNode(int value)

{

	BinaryTreeNode* pNode = new BinaryTreeNode();

	pNode->m_nValue = value;

	pNode->m_pLeft = NULL;

	pNode->m_pRight = NULL;



	return pNode;

}



void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)

{

	if(pParent != NULL)

	{

		pParent->m_pLeft = pLeft;

		pParent->m_pRight = pRight;

	}

}



void PrintTreeNode(BinaryTreeNode* pNode)

{

	if(pNode != NULL)

	{

		printf("value of this node is: %d
", pNode->m_nValue); if(pNode->m_pLeft != NULL) printf("value of its left child is: %d.
", pNode->m_pLeft->m_nValue); else printf("left child is null.
"); if(pNode->m_pRight != NULL) printf("value of its right child is: %d.
", pNode->m_pRight->m_nValue); else printf("right child is null.
"); } else { printf("this node is null.
"); } printf("
"); } void PrintTree(BinaryTreeNode* pRoot) { PrintTreeNode(pRoot); if(pRoot != NULL) { if(pRoot->m_pLeft != NULL) PrintTree(pRoot->m_pLeft); if(pRoot->m_pRight != NULL) PrintTree(pRoot->m_pRight); } } void DestroyTree(BinaryTreeNode* pRoot) { if(pRoot != NULL) { BinaryTreeNode* pLeft = pRoot->m_pLeft; BinaryTreeNode* pRight = pRoot->m_pRight; delete pRoot; pRoot = NULL; DestroyTree(pLeft); DestroyTree(pRight); } }

ファイルcpp
 
 
#include "BinaryTree.h"

#include <iostream>

#include <stack>

using namespace std;



/*   */

void PreOrderTraverseTree(BinaryTreeNode *pRoot)

{

	if (pRoot != NULL)

	{

		cout << pRoot->m_nValue << " ";

		PreOrderTraverseTree(pRoot->m_pLeft);

		PreOrderTraverseTree(pRoot->m_pRight);

	}

}



/*   */

void PreOrderTraverseTreeNoRecursive(BinaryTreeNode *pRoot)

{

	if (pRoot == NULL)

	{

		return;

	}



	stack<BinaryTreeNode *> nodes;

	nodes.push(pRoot);

	while (!nodes.empty())

	{

		BinaryTreeNode *pNode = nodes.top();

		nodes.pop();

		cout << pNode->m_nValue << " ";



		if (pNode->m_pRight != NULL)

		{

			nodes.push(pNode->m_pRight);

		}

		if (pNode->m_pLeft != NULL)

		{

			nodes.push(pNode->m_pLeft);

		}

	}

}



/*   */

void InOrderTraverseTree(BinaryTreeNode *pRoot)

{

	if (pRoot != NULL)

	{

		InOrderTraverseTree(pRoot->m_pLeft);

		cout << pRoot->m_nValue << " ";

		InOrderTraverseTree(pRoot->m_pRight);

	}

}



/*   */

void InOrderTraverseTreeNoRecursive(BinaryTreeNode *pRoot)

{

	if (pRoot == NULL)

	{

		return;

	}



	stack<BinaryTreeNode *> nodes;

	BinaryTreeNode *pCurrent = pRoot;

	while (!nodes.empty() || pCurrent != NULL)

	{

		if (pCurrent != NULL)

		{

			nodes.push(pCurrent);

			pCurrent = pCurrent->m_pLeft;

		}

		else

		{

			pCurrent = nodes.top();

			nodes.pop();

			cout << pCurrent->m_nValue << " ";

			pCurrent = pCurrent->m_pRight;

		}

	}

}



/*   */

void PostOrderTraverseTree(BinaryTreeNode *pRoot)

{

	if (pRoot != NULL)

	{

		PostOrderTraverseTree(pRoot->m_pLeft);

		PostOrderTraverseTree(pRoot->m_pRight);

		cout << pRoot->m_nValue << " ";

	}

}



/*   */

void PostOrderTraverseTreeNoRecursive(BinaryTreeNode *pRoot)

{

	if (pRoot == NULL)

	{

		return;

	}



	stack<BinaryTreeNode *> traverseNodes;

	stack<BinaryTreeNode *> nodes;

	traverseNodes.push(pRoot);

	while (!traverseNodes.empty())

	{

		BinaryTreeNode *pNode = traverseNodes.top();

		traverseNodes.pop();

		if (pNode->m_pLeft != NULL)

		{

			traverseNodes.push(pNode->m_pLeft);

		}

		if (pNode->m_pRight != NULL)

		{

			traverseNodes.push(pNode->m_pRight);

		}

		nodes.push(pNode);

	}



	while (!nodes.empty())

	{

		BinaryTreeNode *pNode = nodes.top();

		nodes.pop();

		cout << pNode->m_nValue << " ";

	}

}



void Test(const char *testName, BinaryTreeNode *pRoot)

{

	if (testName != NULL)

	{

		cout << testName << " : " << endl;

	}

	cout << " :  " ;

	PreOrderTraverseTree(pRoot);

	cout << endl;

	cout << " :";

	PreOrderTraverseTreeNoRecursive(pRoot);

	cout << endl;

	cout << " :  ";

	InOrderTraverseTree(pRoot);

	cout << endl;

	cout << " :";

	InOrderTraverseTreeNoRecursive(pRoot);

	cout << endl;

	cout << " :  ";

	PostOrderTraverseTree(pRoot);

	cout << endl;

	cout << " :";

	PostOrderTraverseTreeNoRecursive(pRoot);

	cout << endl;

}

void Test1()

{

	BinaryTreeNode *pNode1 = CreateBinaryTreeNode(1);

	BinaryTreeNode *pNode2 = CreateBinaryTreeNode(2);

	BinaryTreeNode *pNode3 = CreateBinaryTreeNode(3);

	BinaryTreeNode *pNode4 = CreateBinaryTreeNode(4);

	BinaryTreeNode *pNode5 = CreateBinaryTreeNode(5);

	BinaryTreeNode *pNode6 = CreateBinaryTreeNode(6);



	ConnectTreeNodes(pNode1, pNode2, pNode3);

	ConnectTreeNodes(pNode2, pNode4, pNode5);

	ConnectTreeNodes(pNode3, pNode6, NULL);



	Test("Test1", pNode1);



	DestroyTree(pNode1);

}



void Test2()

{

	BinaryTreeNode *pNode1 = CreateBinaryTreeNode(1);

	BinaryTreeNode *pNode2 = CreateBinaryTreeNode(2);

	BinaryTreeNode *pNode3 = CreateBinaryTreeNode(3);

	BinaryTreeNode *pNode4 = CreateBinaryTreeNode(4);

	BinaryTreeNode *pNode5 = CreateBinaryTreeNode(5);

	ConnectTreeNodes(pNode1, pNode2, NULL);

	ConnectTreeNodes(pNode2, pNode3, NULL);

	ConnectTreeNodes(pNode3, pNode4, NULL);

	ConnectTreeNodes(pNode4, pNode5, NULL);



	Test("Test2", pNode1);



	DestroyTree(pNode1);

}



void Test3()

{

	BinaryTreeNode *pNode1 = CreateBinaryTreeNode(1);

	BinaryTreeNode *pNode2 = CreateBinaryTreeNode(2);

	BinaryTreeNode *pNode3 = CreateBinaryTreeNode(3);

	BinaryTreeNode *pNode4 = CreateBinaryTreeNode(4);

	BinaryTreeNode *pNode5 = CreateBinaryTreeNode(5);

	ConnectTreeNodes(pNode1, NULL, pNode2);

	ConnectTreeNodes(pNode2, NULL, pNode3);

	ConnectTreeNodes(pNode3, NULL, pNode4);

	ConnectTreeNodes(pNode4, NULL, pNode5);



	Test("Test3", pNode1);



	DestroyTree(pNode1);

}



void Test4()

{

	BinaryTreeNode *pNode1 = CreateBinaryTreeNode(1);

	Test("Test4", pNode1);

	DestroyTree(pNode1);

}



void Test5()

{

	Test("Test5", NULL);

}



int main()

{

	Test1();

	Test2();

	Test3();

	Test4();

	Test5();

}

テスト結果: