從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。
打印出和與輸入整數(shù)相等的所有路徑。
例如 輸入整數(shù)22和如下二元樹
則打印出兩條路徑：10, 12和10, 5, 7。
先序遍歷樹即可得到結(jié)果。
算法: FindPath(BTree * root,int sum,int target,Stack * s) 用來計算，sum為棧中的元素的和，target為目標值。
到達一個節(jié)點之后計算當前節(jié)點和sum的和，如果為target，輸出路徑返回，如果大于target，則直接返回，如果小于，則將當前節(jié)點的值入棧，更新sum的值，繼續(xù)遍歷，遍歷完成之后，也就是從當前節(jié)點返回的時候，將其從棧中彈出，更新sum
代碼如下（GCC編譯通過）：
#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("二叉樹內(nèi)元素升序排列："); Iorder(root); printf("/n"); printf("目標值：%d,路徑：",target); FindPath(root,0,target,&stack); printf("/n"); return 0;} //根據(jù)數(shù)組生成二叉排序樹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)];}
