【游戏算法】在二元树中找出和为某一值的所有路径

输入一个整数和一棵二元树，从树的根结点开始往下访问，一直到叶结点所经过的所有结点形成一条路径，打印出和与输入整数相等的所有路径。例如，输入整数 9 和如下二元树：

则打印出两条路径：3，6 和 3，2，4

【答案】

typedef struct path 
{ 
     BiTNode* tree;  	        //结点数据成员 
     struct path* next;  	 
}PATH,*pPath; 	 	 	 	//结点指针成员 

//初始化树的结点栈： 
void init_path( pPath* L ) 
{ 
     *L = ( pPath )malloc( sizeof( PATH ) ); 
     ( *L )->next = NULL;  
} //创建空树 

//树结点入栈函数： 
void push_path(pPath H, pBTree T) 
{ 
     pPath p = H->next; 
     pPath q = H; 
     while( NULL != p ) 
     { 
 	q = p; 
 	p = p->next; 
    } 
    p = ( pPath )malloc( sizeof( PATH ) ); //申请新结点 
    p->next = NULL; 	 	 	 //初始化新结点 
} 

p->tree = T;  
q->next = p;  	 	 	 	 //新结点入栈 

//树结点打印函数： 
void print_path( pPath L ) 
{ 
     pPath p = L->next;  
 
     while( NULL != p ) 	 	 	 
     { 
          printf("%d, ", p->tree->data);   
          p = p->next;  
     }  
} //打印当前栈中所有数据 

///树结点出栈函数： 
void pop_path( pPath H ) 
{
	pPath p = H->next; 
	pPath q = H; 
	if( NULL == p )  	 	    //检验当前栈是否为空 
 	{ 
 	    printf("Stack is null!\n"); 
 	    return; 
	} 
	p = p->next; 
	while( NULL != p ) 	 	     //出栈 
	{ 
 	    q = q->next;  	
 	    p = p->next; 
	} 
	free( q->next );  	 	    //释放出栈结点空间 
	q->next = NULL;  
}			

//判断结点是否为叶子结点： 
int IsLeaf(pBTree T) 
{ 
     return ( T->lchild == NULL )&&( T->rchild==NULL );  
} 

//查找符合条件的路径： 
int find_path(pBTree T, int sum, pPath L) 
{ 
 	push_path( L, T); record += T->data;  
 	if((record == sum ) && (IsLeaf(T)))     //打印符合条件的当前路径 
	{ 
 	    print_path( L );  
 	    printf( "\n" );  
	} 
	if( T->lchild != NULL ) 	 	     //递归查找当前节点的左孩子 
	{ 
 	    find_path( T->lchild, sum, L); 
	} 
	if( T->rchild != NULL )  	 	     //递归查找当前节点的右孩子 
	{ 
 	    find_path( T->rchild, sum, L); 
	} 
	record -= T->data;  pop_path(L);  return 0; 	
}

注意：数据结构一定要活学活用，例如本题，把所有的结点都压入栈，而不符合条件的结点弹出栈，很容易实现了有效路径的查找。虽然用链表也可以实现，但是用栈更利于理解这个问题，即适当的数据结构为更好的算法设计提供了有利的条件。