이원 트리와 한 값의 모든 경로 (귀속 및 비귀속 방법)

제목: 정수와 이원수 한 그루를 입력하십시오.나무의 뿌리 결점에서 잎 결점이 지나갈 때까지 아래로 접근하는 모든 결점이 하나의 경로를 형성한다.입력 정수와 같은 모든 경로를 인쇄합니다.
예를 들어 정수 22와 다음과 같은 이원 트리를 입력한다
                                            10                                           /  \                                          5     12                                        / \                                         　4     7 
10, 12, 10, 5, 7 두 경로가 인쇄됩니다.
귀속 방법: 이 코드는 주해도의 블로그에서 전해졌으며, 상세한 설명은 참고 문헌을 보십시오.

struct BinaryTreeNode // a node in the binary tree
{
      int              m_nValue; // value of node
      BinaryTreeNode  *m_pLeft;  // left child of node
      BinaryTreeNode  *m_pRight; // right child of node
};

///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
(
      BinaryTreeNode*   pTreeNode,    // a node of binary tree
      int               expectedSum,  // the expected sum
      std::vector<int>& path,         // a path from root to current node
      int              currentSum    // the sum of path
)
{
      if(!pTreeNode)
            return;

      currentSum += pTreeNode->m_nValue;
      path.push_back(pTreeNode->m_nValue);

      // if the node is a leaf, and the sum is same as pre-defined, 
      // the path is what we want. print the path
      bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
      if(currentSum == expectedSum && isLeaf)
      {    
           std::vector<int>::iterator iter = path.begin();
           for(; iter != path.end(); ++ iter)
                 std::cout << *iter << '\t';
           std::cout << std::endl;
      }

      // if the node is not a leaf, goto its children
      if(pTreeNode->m_pLeft)
            FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
      if(pTreeNode->m_pRight)
            FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

      // when we finish visiting a node and return to its parent node,
      // we should delete this node from the path and 
      // minus the node's value from the current sum
       path.pop_back();
} 

비귀속적 방법
비귀속적인 방법을 사용할 때 주의해야 한다. 내가 여기서 사용하는 것은 뒷걸음질이다. 뒷걸음질만 부모 노드를 마지막에 저장할 수 있고 아버지 노드는 경로에서 매우 중요한 노드이기 때문에 함부로 삭제할 수 없다.다음에 잎 노드를 훑어보았을 때 판단을 할 수 있다. 만약에 이 노드가 잎 노드이고 총계가 주어진 것과 같다면 출력이다.이때 경로는 마침 우리의 창고에 저장되어 있다.

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

typedef struct BinTreeNode{
	char data;
	BinTreeNode *lChild;
	BinTreeNode *rChild;
}*BiTree;

// 
void createBinTree( BiTree &T, const string &str, int *index )
{
	if ( *index < str.size() )
	{
		char tmpChar = str[(*index)++];
		if ( tmpChar  == '#' )    T = NULL;
		else {
			if (!( T = new BinTreeNode ) ) throw runtime_error("error!");
			T->data = tmpChar;
			createBinTree(T->lChild, str, index );
			createBinTree(T -> rChild, str, index );
			
		}
	}
}


void FindPath( BinTreeNode *pRoot, int expectedSum )
{
	if ( pRoot == NULL )
		return;
	vector<BinTreeNode *> vTree;
	BinTreeNode *pTemp = pRoot;
	BinTreeNode *isViseted = NULL;
	int currentSum = 0;

	while ( pTemp || !vTree.empty())
	{
		if ( pTemp != NULL )
		{
			vTree.push_back( pTemp );
			currentSum += pTemp->data;
			pTemp = pTemp ->lChild;
		}
		else
		{
			pTemp = vTree.back();
			if ( pTemp -> rChild == NULL || pTemp ->rChild == isViseted )
			{
				// 
				if ( pTemp -> lChild == NULL && 
					pTemp -> rChild == NULL &&
					currentSum == expectedSum )
				{
					for (int i = 0; i < vTree.size(); ++i)
						cout<<vTree[i]->data<<' ';
					cout<<endl;
				}

				isViseted = pTemp;
				currentSum -= pTemp->data;
				pTemp = NULL;
				vTree.pop_back();

			}
			else
				pTemp = pTemp -> rChild;
		}
	}

}


int _tmain(int argc, _TCHAR* argv[])
{
	string str="AB#D##C##";    //   
	int index=0;  
	BinTreeNode *T;  
	createBinTree(T,str,&index);  

	int sum = 'A' + 'B' + 'D';
	FindPath(T,sum);
	return 0;
}

참고 문헌:
http://zhedahht.blog.163.com/blog/static/254111742007228357325/