从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
则打印出两条路径：10, 12和10, 5, 7。
先序遍历树即可得到结果。
算法: FindPath(BTree * root,int sum,int target,Stack * s) 用来计算，sum为栈中的元素的和，target为目标值。
到达一个节点之后计算当前节点和sum的和，如果为target，输出路径返回，如果大于target，则直接返回，如果小于，则将当前节点的值入栈，更新sum的值，继续遍历，遍历完成之后，也就是从当前节点返回的时候，将其从栈中弹出，更新sum
代码如下（GCC编译通过）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 8
typedef struct node
{
int data;
struct node * left;
struct node * right;
}BTree;
typedef struct
{
int top;
int data[MAXSIZE];
}Stack;
BTree * CreatTree(int a[],int n);
void Iorder(BTree * root);
void Porder(BTree * root);
void FindPath(BTree * root,int sum,int target,Stack * stack);
void InitStack(Stack * stack);
void Push(Stack * s,int val);
int Pop(Stack *s);
int main(void)
{
int array[MAXSIZE] = {5,3,8,7,2,4,1,9},target;
BTree * root;
Stack stack;
target = 12;
root = CreatTree(array,MAXSIZE);
InitStack(&stack);
Iorder(root);
printf("\n");
printf("目标值：%d,路径：",target);
FindPath(root,0,target,&stack);
printf("\n");
return 0;
}
//根据数组生成二叉排序树
BTree * CreatTree(int a[],int n)
{
BTree * root ,*p,*cu,*pa;
int i;
root = (BTree *)malloc(sizeof(BTree));
root->data = a[0];
root->left = root->right =NULL;
for(i=1;i<n;i++)
{
p = (BTree *)malloc(sizeof(BTree));
p->data = a[i];
p->left = p->right =NULL;
cu = root;
while(cu)
{
pa = cu;
if(cu->data > p->data)
cu = cu->left;
else
cu = cu->right;
}
if(pa->data > p->data)
pa->left = p;
else
pa->right = p;
}
return root;
}
//中根遍历，打印二叉树
void Iorder(BTree * root)
{
if(root)
{
Iorder(root->left);
printf("%3d",root->data);
Iorder(root->right);
}
}
//寻找路径
void FindPath(BTree * root,int sum,int target,Stack * s)
{
int i;
if(!root)
return ;
if(sum + root->data == target)
{
Push(s,root->data);
for(i = 0;i<s->top;i++)
printf("%3d",s->data[i]);
return;
}
else if(sum + root->data > target)
{
return;
}
else
{
Push(s,root->data);
sum += root->data;
FindPath(root->left,sum,target,s);
FindPath(root->right,sum,target,s);
sum -= root->data;
Pop(s);
}
}
//初始化栈
void InitStack(Stack * s)
{
s->top = 0;
}
//入栈
void Push(Stack *s,int val)
{
if(s->top == MAXSIZE)
{
printf("栈满，无法入栈！\n");
return;
}
s->data[(s->top)++] = val;
}
//出栈
int Pop(Stack *s)
{
if(s->top == 0)
{
printf("栈空，无法出栈!\n");
return;
}
return s->data[--(s->top)];
}
|