在二元树中找出和为某一值的所有路径

在二元树中找出和为某一值的所有路径

题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数 22 和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12 和 10, 5, 7。
代码思路
1）递归前序创建二叉树
2）借鉴二叉树的前序遍历，然后加递归，回溯算法。
代码c语言实现
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
int k = 0;
typedef struct BSTreeNode
{
int date;
struct BSTreeNode *leftnode;
struct BSTreeNode *rightnode;
}BSTree;
BSTree *creatree()
{
int num;
BSTree *node;
scanf("%d", &num);
if (num==0)
{
node = NULL;
}
else
{
node = (BSTree *)malloc(sizeof(BSTree));
node->date = num;
node->leftnode=creatree();
node->rightnode=creatree();
}
return node;
}
void printree(BSTree *node)
{
printf("%d ", node->date);
}
void inorder(BSTree *node, void(*visit)(BSTree *))
{
if (node)
{
inorder(node->leftnode, visit);
visit(node);
inorder(node->rightnode, visit);
}
}
void path(BSTree *node, int n, int num,int *p)
{
if (node)
{
n = n - node->date;
p[num++] = node->date;
if (node->leftnode == NULL&&node->rightnode == NULL&&n == 0)
{
printf("第%d组路径: ", ++k);
for (int i=num - 1; i >= 0; i--)
{
printf("%d ", p[i]);
}
printf("\n");
}
else
{
if (node->leftnode != NULL)
{
path(node->leftnode, n, num, p);
}
if (node->rightnode != NULL)
{
path(node->rightnode, n,num, p);
}
}
num--;
n = n + node->date;
}
}
void initree(BSTree *root)
{
root=NULL;
}
void main()
{
int n = 22;
int num = 0;
int a[10] = { 0 };
BSTree *root;
root=creatree();
printf("中序遍历为：\n");
inorder(root, printree);
printf("\n");
path(root, n, num, a);
system("pause");
}

本文永久更新链接地址：