리프 노드에 루트에서 모든 경로를 얻기

Question

  a 
     / \ 
     a  a 
    /\ /\ 
    a c a f 
    /\ /\ 
    b d e g 

나는이 연결된 구조로 표현 위처럼 보이는 나무 :

class Node 
    { 
     Node* leftChild; 
     Node* rightChild; 
     char data; 
    } 

class Tree 
{ 
    Node* root; 
} 

내 목표는 잎에 루트에서 모든 경로를 찾을 수 있습니다 노드.

내 트리 탐색 알고리즘은 다음과 같습니다

void inorder() 
    { 
    in(root); 
    } 

    void in(CharNode* currentNode) 
    { 
    if(currentNode) 
     { 
     in(currentNode->leftChild); 
     cout << currentNode->data << endl; 
     in(currentNode->rightChild); 
     } 
    } 

내가 이것을 실행할 때, 그림과 같이 나무가 건설되고 긍정적입니다. 나는 그것을 시험했다. 그러나 왜 내 트래버스 세분화 오류가 발생하는지 파악할 수 없습니다.

내가 얻을 출력은 다음과 같습니다

b 

Segmentation fault. 

나는 작은 높이 나무에 테스트 한, 그것은 작동합니다. 그러나 어떤 이유로 그것은 2보다 큰 높이의 나무에서는 작동하지 않습니다. 나무가 잘못되어 있다고 생각했습니다. 나는 각 부모, 왼쪽 자식 및 오른쪽 자식을 인쇄하고 그림과 같이 인쇄했습니다. . 그래서 그것은 순회 알고리즘입니다.

Answer 1

트리를 빌드 할 때 노드에서 leftChild 및 rightChild를 NULL (0)으로 초기화해야합니다. 이는 리프 노드와 leftChild 또는 rightChild가없는 노드에 중요합니다.

class Node 
     : leftChild(0) 
     , rightChild(0) 
     , data(0) 
{ 
    Node* leftChild; 
    Node* rightChild; 
    char data; 
} 

Answer 2

/* 
** Binary Tree Problems 
** Printing all Root to Leaf paths in a Binary Tree 
*/ 

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

# define SIZE 20 
# define MAX(A,B) A>B?A:B; 

typedef struct BinaryTree 
{ 
    int data; 
    struct BinaryTree *left; 
    struct BinaryTree *right; 
}BST; 

int A[SIZE]={10,12,15,17,8,18,9,3,11,14,2,1,16,10}; 
int no_of_nodes=14; 



BST* newNode(int data) 
{ 
    BST *node; 

    node=(BST *)malloc(sizeof(BST)); 
    if(!node) 
     return NULL; 

    node->data = data; 
    node->left=NULL; 
    node->right=NULL; 

    return node; 
} 

BST *Insert(BST *root,int d,int l) 
{ 
    if(root==NULL) 
     return(newNode(d)); 

    else 
    { 
     if(d < root->data) 
      root->left=Insert(root->left,d,++l); 
     else 
      root->right=Insert(root->right,d,++l); 

     return(root); 
    } 
} 


BST* CreateTree(BST *root1) 
{ 
    int i=0; 

    for(i=0;i<no_of_nodes;i++) 
    { 
     root1=Insert(root1,A[i],1); 
    } 

    return(root1); 
} 

void Inorder(BST *root1) 
{ 
    if(root1==NULL) 
     return; 

    Inorder(root1->left); 
    printf(" %3d ", root1->data); 
    Inorder(root1->right); 
} 

void Preorder(BST *root1) 
{ 
    if(root1==NULL) 
     return; 

    printf(" %3d ", root1->data); 
    Preorder(root1->left); 
    Preorder(root1->right); 
} 

void PrintArr(int *arr,int len) 
{ 
    static int pathNo=0; 
    int i; 

    printf("\nPath %d ->",++pathNo); 

    for(i=0;i<len;i++) 
     printf(" %d ",arr[i]); 

    return; 
} 

void PrintR2LPaths(BST *root,int pathArr[],int pathLen) 
{ 
    if(root==NULL) 
     return; 

    pathArr[pathLen]=root->data; 
    pathLen++; 

    if(root->left==NULL && root->right==NULL) 
    { 
     PrintArr(pathArr,pathLen); 
     return; 
    } 
    else 
    { 
     PrintR2LPaths(root->left,pathArr,pathLen); 
     PrintR2LPaths(root->right,pathArr,pathLen); 
    } 
} 

int main() 
{ 
    int result=0; 
    BST *root1=NULL; 
    int pathArr[SIZE]; 

    root1=CreateTree(root1); 

    printf("\n\n---------------------------------------------------\n"); 

    printf("\n\nPreorder Traversal of Tree : "); 
    Preorder(root1); 

    printf("\n\nInorder Traversal of Tree : "); 
    Inorder(root1); 

    printf("\n\n---------------------------------------------------\n"); 

    printf("\nPrinting Paths\n\n"); 
    PrintR2LPaths(root1,pathArr,0); 

    printf("\n\n---------------------------------------------------\n"); 
    getchar(); 

    return(0); 
}