이원 수 에서 어떤 값 의 모든 길 을 찾 아 라.

정수 하나 와 이원 나 무 를 입력 하 세 요.나무의 뿌리 결점 부터 아래로 내 려 가서 잎 결점 이 지나 가 는 모든 결점 이 하나의 경 로 를 형성한다.입력 정수 와 같은 모든 경 로 를 출력 합 니 다.예 를 들 어 정수 22 와 다음 이원 트 리 를 입력 하 십시오.   10    / \   5  12  / \ / \
 4 7 8 9
10, 12, 10, 5, 7 두 경 로 를 출력 합 니 다.이원 트 리 노드 의 데이터 구 조 는 structBinary TreeNode / a nodein thebinary tree {intm nValue; / / value of node Binary TreeNode * m pLeft; / / left childof node Binary TreeNode * m pRight; / right childof node
structBinaryTreeNode // a nodein thebinarytree { intm_nValue; // valueof node BinaryTreeNode *m_pLeft; // leftchildof node BinaryTreeNode *m_pRight; //right childof node
}

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

#define MAX 20  
  
typedef struct BiTreeNode  
{  
    int data;  
    struct BiTreeNode *left;  
    struct BiTreeNode *right;  
}BiTreeNode_T;  
  
/*     */  
BiTreeNode_T * CreateBSTree(int *data,int pos,int len)  
{  
    BiTreeNode_T * tr;  
    if(pos>=len)  
    {  
        return NULL;  
    }  
    else  
    {  
        tr = (BiTreeNode_T *)malloc(sizeof(BiTreeNode_T));  
        tr->data = data[pos];  
        tr->left =  CreateBSTree(data, 2*pos+1, len);  
        tr->right = CreateBSTree(data, 2*pos+2, len);    
        return tr;  
    }  
}  
  
//         
void InOrderTraverse(BiTreeNode_T *root)  
{  
    if(root !=NULL)  
    {  
        InOrderTraverse(root->left);   
		
		if(NULL != root->left || NULL != root->right)
			printf("%d not leaf node
", root->data);
		else
			printf("%d 
",root->data);
		
        InOrderTraverse(root->right);  
    }  
}  
  
//      
void printPath(int path[], int top)  
{  
	int i = 0;
    for(i=0; i<top; i++)  
        printf("%d ", path[i]); 
	
    printf("
");  
}  
  
//    sum   ,path        ，top                 
void findPath(BiTreeNode_T *root, int sum, int top, int path[])  
{  
    path[top++] = root->data;  
    sum -= root->data;  
      
    if (root->left == NULL && root->right==NULL)   
    {  
        /*      */
        if (sum == 0)   
        {  
            printPath(path, top);
			top--;
			sum += root->data;
        }  
    }   
    else   
    {   
        /*       */
        if(sum <= 0)   
        {  
            if(sum == 0) 
               printPath(path, top);
			top--;
			sum += root->data;
			return;
        }
        
        if (root->left != NULL)   
               findPath(root->left, sum, top, path);  
		
        if (root->right!=NULL)   
               findPath(root->right, sum, top, path);  
    }    
}  
  
int main()  
{  
    int data[]={10, 5, 12, 15, 7, 8, 9};  
    int len=sizeof(data)/sizeof(int);  
  
    BiTreeNode_T * root = CreateBSTree(data, 0, len);   
    InOrderTraverse(root);  
    printf("
");  
      
    int sum=22;  
    int top=0;  
    int path[MAX] = {0};  
	printf("-------------------------------------
");
    findPath(root, sum, top, path);  
    return 0;  
}  
/*
  
4 
5 not leaf node
7 
10 not leaf node
8 
12 not leaf node
9 

-------------------------------------
10 5 7 
10 12

*/