在二叉树中找出和为某一值的所有路径（二叉树路径和等于指定值c）

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数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); printf("二叉树内元素升序排列："); 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)]; }