#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("目標(biāo)值：%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)];
}