输入一个二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
创新互联是一家专注于成都网站制作、成都网站设计、
外贸营销网站建设与策划设计,彭山网站建设哪家好?
创新互联做网站,专注于网站建设十余年,网设计领域的专业建站公司;建站业务涵盖:彭山等地区。彭山做网站价格咨询:028-86922220
如上图的二叉树，当输入根结点和一个数值12的时候，就有两条路径“1->2->4->5”和“1->3->8”，如果存在，就输出上述路径，如果没有任何一条路径满足就不输出路径并提示；
首先，路径一定是从根结点开始到某个叶子结点结束，这才是一条路径，因此，应该最先访问的就是根结点，而在二叉树的先中后序遍历中只有先序遍历是最先访根结点的，所以可以用如下方法：用先序遍历方法遍历二叉树，每当经过一个结点的时候就将其值进行保存相加，如果中途发现或者到达叶子结点之后，当前路径相加得到的值并不满足要求的值，则往回退并将值减去，或者当前路径已经满足，则需要再去换一条路径访问看是否还有其他路径满足条件，而能够提供往回退的方法就只有递归了，直至遍历完毕二叉树；
程序设计如下：
#include
#include
#include
using namespace std;
struct BinaryTreeNode//二叉树结点数据结构
{
int _val;
BinaryTreeNode *_Lnode;
BinaryTreeNode *_Rnode;
BinaryTreeNode(int val)
:_val(val)
,_Lnode(NULL)
,_Rnode(NULL)
{}
};
BinaryTreeNode* _Create(int *arr, size_t& index, size_t size)//创建二叉树
{
if((index < size) && (arr[index] != '#'))
{
BinaryTreeNode *root = new BinaryTreeNode(arr[index]);
root->_Lnode = _Create(arr, ++index, size);
root->_Rnode = _Create(arr, ++index, size);
return root;
}
else
return NULL;
}
BinaryTreeNode* CreateBinaryTree(int *arr, size_t size)
{
assert(arr && size);
size_t index = 0;
return _Create(arr, index, size);
}
void DestoryBinaryTree(BinaryTreeNode *root)//销毁二叉树
{
if(root != NULL)
{
DestoryBinaryTree(root->_Lnode);
DestoryBinaryTree(root->_Rnode);
delete root;
}
}
void PrevOrder(BinaryTreeNode *root)//前序遍历打印出二叉树
{
if(root != NULL)
{
cout<_val<<" ";
PrevOrder(root->_Lnode);
PrevOrder(root->_Rnode);
}
}
void _Count(BinaryTreeNode* root, vector *pv, int& count, int num)
{
if(root != NULL)
{
count += root->_val;//每当一个结点不为NULL的时候，就将其放入容器中且加上其值
(*pv).push_back(root->_val);
_Count(root->_Lnode, pv, count, num);
_Count(root->_Rnode, pv, count, num);
if(count == num)//当找到一个路径的时候就将其打印出来
{
cout<<"A Path Is : ";
for(size_t i = 0; i < (*pv).size(); ++i)
cout<<(*pv)[i]<<"->";
cout<<"NULL"< v;//用一个容器来存放路径
int count = 0;//用一个计数器计算和
_Count(root, &v, count, num);
}
int main()
{
int arr[] = {1,2,6,'#','#',4,5,'#','#','#',3,7,'#','#',8,'#','#'};
int num = 12;
BinaryTreeNode *root = CreateBinaryTree(arr, sizeof(arr)/sizeof(arr[0]));
cout<<"PrevOrder:";
PrevOrder(root);
cout<运行程序：
《完》
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
当前标题：二叉树中和为某一值的路径——25-创新互联
网站路径：http://bzwzjz.com/article/jggjo.html
