C++バージョンの二叉木の遍歴原理の説明とコードの実現

C++バージョンの二叉木の遍歴原理の説明とコードの実現

1.広さ優先

2.深度優先

3.遍歴(先/中/後順)

3.1再帰

3.2非再帰

1.広さ優先

/*
*    
*/
struct Node
{
	int data;//   
	Node* left;//   
	Node* right;//   
};

/*!
* \brief         
* \param pTree : Node *    
* \returns void :
* \throws 
* \remarks
* \see
*/
void BreadthFirstSearch(Node* pTree)
{
	/*
				   A
				 /   \
			   B       C
			  / \     / \
			 D   E   F   G

	    ：A B C D E F G
	*/

	/*
	    ：
		1.     
		2.     
		3.     

		           ，       ，       
	*/

	if (pTree == nullptr)
		return;

	queue<Node*>queueNode;
	queueNode.push(pTree);
	Node* pNode;
	while (!queueNode.empty())
	{
		pNode = queueNode.front;
		queueNode.pop();
		std::cout << pNode->data << std::endl;
		if (pNode->left != nullptr)
			queueNode.push(pNode->left);
		if (pNode->right != nullptr)
			queueNode.push(pNode->right);
	}
}

2.深さ優先

/*
*    
*/
struct Node
{
	int data;//   
	Node* left;//   
	Node* right;//   
};

/*!
* \brief         
* \param pTree : Node *    
* \returns void : 
* \throws 
* \remarks 
* \see 
*/
void DepthFirstSearch(Node* pTree)
{
	/*
	     A              
				 /   \
			   B       C
			  / \     / \
			 D   E   F   G
	
	    ：A B D E C F G	
	*/

	/*
	    ：
		1.     
		2.     
		3.     

		          ，       ，       
	*/

	if (pTree == nullptr)
		return;

	stack<Node*>stackNode;
	stackNode.push(pTree);
	Node* pNode;
	while (!stackNode.empty())
	{
		pNode = stackNode.top();
		std::cout << pNode->data << std::endl;
		stackNode.pop();
		if (pNode->right != nullptr)
			stackNode.push(pNode->right);
		if (pNode->left != nullptr)
			stackNode.push(pNode->left);		
	}
}

3.遍歴(先/中/後順)
3.1再帰

/*
*    
*/
struct Node
{
	int data;//   
	Node* left;//   
	Node* right;//   
};


#include 
#include 

/*!
* \brief          （ / /  ）  
* \param pHead : Node *   
* \returns void : 
* \throws 
* \remarks 
* \see 
*/
void Traversal(Node* pHead)
{
	if (pHead == nullptr)
		return;

	//
	//    （     ）
	std::cout << pHead->data << std::endl;
	Traversal(pHead->left);
	Traversal(pHead->right);

	//
	//    （     ）
	Traversal(pHead->left);
	std::cout << pHead->data << std::endl;
	Traversal(pHead->right);

	//
	//    （     ）
	Traversal(pHead->left);
	Traversal(pHead->right);
	std::cout << pHead->data << std::endl;
}

3.2非再帰

/*
*    
*/
struct Node
{
	int data;//   
	Node* left;//   
	Node* right;//   
};


#include 
#include 
/*!
* \brief               
* \param pHead : Node *   
* \returns void :
* \throws 
* \remarks     （     ）
* \see
*/
void TraversalPre(Node* pHead)
{
	if (pHead == nullptr)
		return;

	std::stack<Node*>stackNode;
	stackNode.push(pHead);
	Node* pNode = pHead;
	while (!stackNode.empty())
	{
		pNode = stackNode.top();
		std::cout << pNode->data << std::endl;
		stackNode.pop();

		if (pNode->right != nullptr)
			stackNode.push(pNode->right);

		if (pNode->left != nullptr)
			stackNode.push(pNode->left);
	}
}


/*!
* \brief               
* \param pHead : Node *   
* \returns void :
* \throws 
* \remarks     （     ）
* \see
*/
void TraversalIn(Node* pHead)
{
	if (pHead == nullptr)
		return;

	std::stack<Node*>stackNode;
	while (!stackNode.empty() || pHead != nullptr)
	{
		if (pHead != nullptr)
		{
			stackNode.push(pHead);
			pHead = pHead->left;
		}
		else
		{
			pHead = stackNode.top();
			std::cout << pHead->data << std::endl;
			stackNode.pop();
			pHead = pHead->right;
		}
	}
}

/*!
* \brief               
* \param pHead : Node *   
* \returns void :
* \throws 
* \remarks     （     ）
* \see
*/
void TraversalPos(Node* pHead)
{
	if (pHead == nullptr)
		return;

	std::stack<Node*>stackNode1;
	std::stack<Node*>stackNode2;
	Node* pNode;

	stackNode1.push(pHead);

	while (!stackNode1.empty())
	{
		pNode = stackNode1.top();
		stackNode2.push(pNode);
		stackNode1.pop();

		if (pNode->left != nullptr)
			stackNode1.push(pNode->left);

		if (pNode->right != nullptr)
			stackNode1.push(pNode->right);
	}

	while (!stackNode2.empty())
	{
		std::cout << stackNode2.top()->data << std::endl;
		stackNode2.pop();
	}
}