이원 트 리 에서 특정한 값 의 모든 경로 (트 리) 를 찾 습 니 다.

제목: 정수 하나 와 이원 수 한 그루 를 입력 하 세 요.나무의 뿌리 결점 부터 아래로 내 려 가서 잎 결점 이 지나 가 는 모든 결점 이 하나의 경 로 를 형성한다.입력 정수 와 같은 모든 경 로 를 출력 합 니 다.예 를 들 어 정수 22 와 다음 이원 트 리 를 입력 하 십시오.  10    / /    5 12    /  /   4     7. 두 가지 경 로 를 출력 합 니 다. 10, 12, 10, 5, 7.
이원 트 리 노드 의 데이터 구 조 는 struct Binary TreeNode / a node in the binary tree {int m nValue; / / value of node Binary TreeNode * m pLeft; / left child of node Binary TreeNode * m pRight; / / right child of node} 로 정의 합 니 다.
알고리즘:
이것 은 재 귀적 인 과정 이다. 즉, 10 - 5 - 4, 10 - 5 - 7, 10 - 12 경로 에서 22 와 같은 것 을 찾 아 매번 잎 노드 에 옮 겨 다 니 며 경 로 를 path 용기 에 저장 하 는 것 이다. 만약 에 잎 노드 의 값 이 22 와 같 으 면 당연히 출력 한다. 그렇지 않 으 면 경로 용기 에서 이 값 을 삭제 하고 구체 적 인 알고리즘 을 사용한다.

#include <iostream>
#include <vector>
using namespace std;

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
};

vector<BinaryTreeNode*> pathVec;

void creatTree(BinaryTreeNode *&root, int *a, int i, int len)
{
	if(i >= len)
		return;
	root = new BinaryTreeNode;
	root->m_nValue = a[i];
	root->m_pLeft = NULL;
	root->m_pRight = NULL;
	creatTree(root->m_pLeft, a, 2*i + 1, len);
	creatTree(root->m_pRight, a, 2*i + 2, len);
}

void preorder(BinaryTreeNode* &root)
{
	if(!root)
		return;
	cout << root->m_nValue << " ";
	preorder(root->m_pLeft);
	preorder(root->m_pRight);	
}

void printPath(vector<BinaryTreeNode*>& pathVec)
{
	for(vector<BinaryTreeNode*>::iterator it = pathVec.begin(); it != pathVec.end(); it++)
		cout << (*it)->m_nValue << " ";
	cout << endl;
}

void pathTree(BinaryTreeNode* &root, int val)
{
//          val     
	static int sum = 0;
	sum += root->m_nValue;
	pathVec.push_back(root);
	if(sum == val && root->m_pLeft == NULL && root->m_pRight == NULL)
		printPath(pathVec);
	if(root->m_pLeft)
		pathTree(root->m_pLeft, val);
	if(root->m_pRight)
		pathTree(root->m_pRight, val);
	sum -= root->m_nValue;
	pathVec.pop_back();
}

int main()
{
	BinaryTreeNode *root = 0;
	int a[] = {10, 5, 12, 7, 8};
	int len = sizeof a / sizeof a[0];
	creatTree(root, a, 0, len);
//	preorder(root);
	pathTree(root, 22);
}