【100题】第四题

题目：输入一个整数和一棵二叉树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出节点和等于输入整数的所有路径。
例如 输入整数22和如下二叉树
10
/ \
5 12
/\
4 7
则打印出两条路径：10, 12和10, 5, 7。

二叉树节点的数据结构定义为：
struct BinaryTreeNode //二叉树节点结构

{
int m_nValue;

BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};

源码：（可以运行，但是还有些问题没搞明白……持续更新中）

#include "stdio.h"
#include "malloc.h"


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


//打印路径
void printPath(BinaryTreeNode *path);
/**
*sum为要求的整数和
*curSum为从根节点到tree父节点，路径上所有数的和
*path指向当前路径的最后一个节点，该路径有BinaryTreeNode组成双向链表
*m_pRight指向路径下一节点，m_pLeft指向上一节点
**/
void searchPath(BinaryTreeNode *tree,BinaryTreeNode *path,int curSum,int sum)
{
curSum += tree->m_nValue;

if(curSum>sum)//路径值已经大于所求和，返回
return;

//如果没有返回 说明 当前值<输入值

BinaryTreeNode *root=new BinaryTreeNode();
//BinaryTreeNode *root=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
// root=NULL;

root->m_nValue=tree->m_nValue;

//将当前节点的值加入到路径中
if(path==NULL)//第一次加入
path=root;
else
{
path->m_pRight=root;
root->m_pLeft=path;
path=root; //采用尾插法，标记的是尾部
}

//如果 当前值=输入值
if(curSum==sum)
{
//路径结束且和=sum，为所求
if(tree->m_pLeft==NULL&&tree->m_pRight==NULL)
{
//获得路径头节点，用于打印
while(path->m_pLeft)
path=path->m_pLeft;
printPath(path);
}
//若当前路径的和=sum，但路径还未到达叶节点，此路径不可行

//delete node;
//free(node);
//node=NULL;
return;
}

//curSum<sum，继续搜寻路径
if(tree->m_pLeft!=NULL)
searchPath(tree->m_pLeft,path,curSum,sum);

if(tree->m_pRight!=NULL)
searchPath(tree->m_pRight,path,curSum,sum);

//delete node;
// free(node);
//node=NULL;
}
void printPath(BinaryTreeNode *path)
{
while(path)
{
printf("%5d",path->m_nValue);
//cout<<path->m_nValue<<" ";
path=path->m_pRight;
}
printf("\n");
//cout<<endl;
}
int main()
{
BinaryTreeNode *root=NULL;

BinaryTreeNode node10;
node10.m_nValue=10;
BinaryTreeNode node5;
node5.m_nValue=5;
BinaryTreeNode node12;
node12.m_nValue=12;

BinaryTreeNode node4;
node4.m_nValue=4;

BinaryTreeNode node7;
node7.m_nValue=7;

node10.m_pLeft=&node5;
node10.m_pRight=&node12;
node5.m_pLeft=&node4;
node5.m_pRight=&node7;

node12.m_pLeft=node12.m_pRight=NULL;
node4.m_pLeft=node4.m_pRight=NULL;
node7.m_pLeft=node7.m_pRight=NULL;

root=&node10;
//BinaryTreeNode *path=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
BinaryTreeNode *path=NULL;
printf("搜寻值为22的路径有如下几条：");
searchPath(root,path,0,22);


}