获取从根节点到叶节点的所有路径

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

/* 
** 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);
}

Answer 2

在构建树时，请确保在节点上将leftChild和rightChild初始化为NULL（0）。这对于叶节点和缺少leftChild或rightChild的节点至关重要。

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