充分利用根的所有路徑葉子節點

  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

充分利用根的所有路徑葉子節點

回答

相關問題