充分利用根的所有路径叶子节点

  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的工作，我认为这是一件与树去错了，我都经历了，并印在每个父母，左子和右孩子和他们打印出如图所示。所以它绝对是遍历算法。

来源

2012-07-29 ordinary

遍历算法，看起来好像没什么问题。发布一个可编辑的例子，我相信这个错误会很快找到。 – jahhaj 2012-07-29 06:45:08

'CharNode'是什么？你确定你正在建造树吗？ – Donotalo 2012-07-29 06:45:22

@Donotalo，他确定，但我怀疑他错了。 – jahhaj 2012-07-29 06:46:04

当你建立你的树，一定要leftChild和rightChild您的节点上初始化为NULL（0）。这对叶节点和缺少leftChild或rightChild的节点至关重要。

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

来源

2012-07-29 06:45:48

就是这样。非常感谢。我不能相信我错过了那么简单的事情。尽管它们未初始化，它们是不是会自动分配给NULL指针？ – ordinary 2012-07-29 06:54:58

在C/C++中不是这样。在Java中是真实的，这可能会导致混淆。 – 2012-07-29 06:55:57

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

来源

2013-08-18 06:48:01

充分利用根的所有路径叶子节点

回答

相关问题