ツリー関連アクション(遍歴、パス、最近の共通親ノード、再構築)

本論文では,二叉木に関する動作をまとめ,最後にすべての動作の実装を添付した.まだ足りないところがあって、後でタイムリーに更新します~
 
関連アクションは次のとおりです.
1、挿入:InsertBTree
2、遍歴
1)前順遍歴(再帰):PreOrderTraverse
2)前順遍歴(非再帰):PreOrderTraverseNoRec
3)中順遍歴(再帰):InOrderTraverse
4)中序遍歴(非再帰):InOrderTraverseNoRec
5)後段遍歴(再帰):PostOrderTraverse
6)後段遍歴(非再帰):PostOrderTraverseNoRec
7)層順遍歴:LevelOrderTraverse
3、ルートノードからあるノードへのパスを探す:FindNodePath
4、2つのノードの最も近い共通の親ノードを探す:FindNearestParent
5、二叉木の再構築
1)前および中順の遍歴結果による再構築:RebuildFromPreAndInOrder
2)後順と中順の遍歴結果による再構築:RebuildFromPostAndInOrder
 
手順は次のとおりです.
 

#include 
#include 
#include 
#include 

using namespace std;

//               
typedef int ElemType;

struct BTreeNode
{
	ElemType elem;		//       
	BTreeNode *left;	//      
	BTreeNode *right;	//      
};

//          ，                 
void InsertBTree(BTreeNode **root, ElemType elem)
{
	//      ，   
	if (*root == NULL)
	{
		*root = new BTreeNode;
		(*root)->elem  = elem;
		(*root)->left  = NULL;
		(*root)->right = NULL;
		return ;
	}

	BTreeNode *node = *root;
	while (node != NULL)
	{
		if (elem < node->elem)
		{
			if (node->left == NULL)
			{
				BTreeNode *temp = new BTreeNode;
				temp->elem  = elem;
				temp->left  = NULL;
				temp->right = NULL;
				node->left  = temp;
				return ;
			} 
			else
			{
				node = node->left;
			}
		} 
		else
		{
			if (node->right == NULL)
			{
				BTreeNode *temp = new BTreeNode;
				temp->elem  = elem;
				temp->left  = NULL;
				temp->right = NULL;
				node->right = temp;
				return ;
			} 
			else
			{
				node = node->right;
			}
		}
	}
}


//     （    ）
void PreOrderTraverse(BTreeNode *root)
{
	if (root != NULL)
	{
		cout<elem<left);	//        
		PreOrderTraverse(root->right);	//        
	}
}

//     （     ）
void PreOrderTraverseNoRec(BTreeNode *root)
{
	stack s;

	while (root!=NULL || !s.empty())
	{
		if (root != NULL)
		{
			cout<elem<left;
		} 
		else
		{
			root = s.top()->right;
			s.pop();
		}
	}
}

//     （    ）
void InOrderTraverse(BTreeNode *root)
{
	if (root != NULL)
	{
		InOrderTraverse(root->left);	//        
		cout<elem<right);	//        
	}
}

//     （     ）
void InOrderTraverseNoRec(BTreeNode *root)
{
	stack s;
	
	while (root!=NULL || !s.empty())
	{
		if (root != NULL)
		{
			s.push(root);
			root = root->left;
		} 
		else
		{
			cout<elem<right;		//  root            
			s.pop();					//       
		}
	}
}

//     （    ）
void PostOrderTraverse(BTreeNode *root)
{
	if (root != NULL)
	{
		PostOrderTraverse(root->left);		//        
		PostOrderTraverse(root->right);		//        
		cout<elem< v;
	v.push_back(root);
	vector::iterator iter = v.end()-1;	//   iter     

	do 
	{
		if (root != NULL)
		{
			if (root->left != NULL)
			{
				iter = v.insert(iter, root->left) + 1;
			}
			if (root->right != NULL)
			{
				iter = v.insert(iter, root->right) + 1;
			}
		}

		iter--;
		root = *iter;

	} while (iter != v.begin()-1);

	//         
	for (iter=v.begin(); iter!=v.end(); iter++)
	{
		cout<elem< q;

	while (root != NULL)
	{
		//       ，                 
		cout<elem<left != NULL)
		{
			q.push(root->left);
		} 
		if (root->right != NULL)
		{
			q.push(root->right);
		}

		if (!q.empty())
		{
			root = q.front();
			q.pop();
		} 
		else
		{
			break;
		}
		
	}
}

//                     
void RebuildFromPreAndInOrder(BTreeNode **root, ElemType preOrder[], ElemType inOrder[], int size)
{
	if (size <= 0)
	{
		return ;
	}

	//           
	*root = new BTreeNode;
	(*root)->elem  = preOrder[0];
	(*root)->left  = NULL;
	(*root)->right = NULL;

	for (int num=0; numleft), preOrder+1, inOrder, num);
	RebuildFromPreAndInOrder(&((*root)->right), preOrder+num+1, inOrder+num+1, size-num-1);
}

//                     
void RebuildFromPostAndInOrder(BTreeNode **root, ElemType postOrder[], ElemType inOrder[], int size)
{
	if (size <=0 )
	{
		return ;
	}

	//           
	*root = new BTreeNode;
	(*root)->elem  = postOrder[size-1];
	(*root)->left  = NULL;
	(*root)->right = NULL;

	for (int num=0; numleft), postOrder, inOrder, num);
	RebuildFromPostAndInOrder(&((*root)->right), postOrder+num, inOrder+num+1, size-num-1);
}


//               ，    vector path  
bool FindNodePath(BTreeNode *root, ElemType elem, vector &path)
{
	//         vector    stack    

	if (root != NULL)
	{
		path.push_back(root);

		if (root->elem == elem)
		{
			//      
			path.assign(path.begin(), path.end());
			return true;
		} 
		else
		{
			if (FindNodePath(root->left, elem, path) == true)
			{
				return true;
			}
			if (FindNodePath(root->right, elem, path) == true)
			{
				return true;
			}
			path.pop_back();
		}
	} 
	
	return false;
}

void FindNearestParent(BTreeNode *root, ElemType elem1, ElemType elem2)
{
	//        elem1 elem2       
	vector path1, path2;
	FindNodePath(root, elem1, path1);
	FindNodePath(root, elem2, path2);

	//                  ，           
	vector::iterator iter1 = path1.begin();
	vector::iterator iter2 = path2.begin();
	while ((*iter1)->elem == (*iter2)->elem)
	{
		iter1++;
		iter2++;
	}
	
	cout<elem< path;	//             
	if (FindNodePath(root, elem, path) == true)
	{
		cout<::iterator iter=path.begin(); iter!=path.end(); iter++)
		{
			cout<elem<

実際に使用したツリーは次のとおりです.
実行結果は次のとおりです.