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

题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
                                            10
                                           /   \
                                          5     12
                                        /   \   
                                     　4     7  
则打印出两条路径：10, 12和10, 5, 7。

 

当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结点并且当前路径的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是根结点到父结点的路径。我们不难看出保存路径的数据结构实际上是一个栈结构，因为路径要与递归调用状态一致，而递归调用本质就是一个压栈和出栈的过程。

 

最近越做这些题越TMD的觉得递归的伟大...

 

 

#include <stdio.h>
#include <stdlib.h>

#define N 5

int current_num = 0;

typedef struct tree
{
  int num;
  struct tree* lchild;
  struct tree* rchild;
}TREE;

typedef struct list
{
   TREE* tree;
   struct list* next;
 }LIST;
 
int add_tree(TREE** T,int num)
{
  if(*T==NULL)
   {
     *T = (TREE*)malloc(sizeof(TREE));
     (*T)->num = num;
     (*T)->lchild = NULL;
     (*T)->rchild = NULL;
   }
  else if((*T)->num < num)
    return add_tree( &((*T)->rchild), num);
  else
    return add_tree( &((*T)->lchild), num);
  
  return 0;
}

void mid_walk_tree(TREE* T)
{
  if(T!=NULL)
   {
      mid_walk_tree(T->lchild);
      printf("%d\t",T->num);
      mid_walk_tree(T->rchild);
    }
}

int IsLeaf(TREE* T)
{
  return (T->lchild==NULL)&&(T->rchild==NULL);
}

void init_list(LIST** L)
{
   *L = (LIST*)malloc(sizeof(LIST));
   (*L)->next = NULL;
 }

/*add tree T to the list's tail*/
void push_list(LIST* H,TREE* T)
{
  LIST* p = H->next;
  LIST* q = H;
  
  while(p!=NULL)
   {
    q = p;
    p = p->next;
  }
    
  p = (LIST*)malloc(sizeof(LIST));
  p->next = NULL;
  p->tree = T;
  
  q->next = p;
}

void print_list(LIST* L)
{
  LIST* p = L->next;
  
  while(p!=NULL)
   {
     printf("%d\t",p->tree->num);
     p = p->next;
    }
}

void pop_list(LIST* H)
{
  LIST* p = H->next;
  LIST* q = H;
  
  if(p==NULL)
   {
    printf("already null\n");
    return;
   }
  p = p->next;
  while(p!=NULL)
   {
    q = q->next;
    p = p->next;
  }
  free(q->next);
  q->next = NULL;
}

int find_path(TREE* T, int expect_num, LIST* L)
{
   push_list( L, T);
   current_num += T->num;
   
   if((current_num == expect_num)&&(IsLeaf(T)))
    {
       print_list(L);
       printf("\n");
     }
    
    if(T->lchild != NULL)
     find_path( T->lchild, expect_num, L);
     
    if(T->rchild != NULL)
     find_path( T->rchild, expect_num, L);
     
   current_num -= T->num;
   pop_list(L);
}
 
int main(int argc, char *argv[])
{
  int i;
  TREE* T = NULL;
  LIST* L = NULL;
  int A[N] = {10,5,12,4,7};
  int expect_num = 22;
 
   
  for(i=0; i<N; i++)
     add_tree(&T, A[i]);
  
  mid_walk_tree(T);
  
  init_list(&L);
  printf("\ninit list ok\n");
  find_path( T, expect_num, L);
  system("PAUSE");    
  return 0;
}