將所有根打印到葉子路徑

我嘗試將所有根打印到二叉樹中的葉子路徑的代碼。將所有根打印到葉子路徑

#include<iostream> 
#include<stack> 
using namespace std; 

bool visited[100]; 
void intilize(){ 
    for(int i=0;i<100;i++) 
     visited[i]=false; 
} 
struct node 
{ 
    int data; 
    struct node *left,*right; 
}; 
struct node* createNode(int k) 
{ 
    struct node* temp = new node; 
    temp->left = NULL; 
    temp->right = NULL; 
    temp->data = k; 
    return temp; 
} 
stack<node*> s,s1; 
void print(){ 
    while(!s.empty()){ 
     s1.push(s.top()); 
     s.pop(); 
    } 
    while(!s1.empty()){ 
     struct node* a= s1.top(); 
     cout<<a->data<<" "; 
     s1.pop(); 
     s.push(a); 
     if(s1.empty()) 
     return; 

    } 


} 
void printpath(struct node* node){ 
    if(node==NULL) return; 
    s.push(node); 

    while(!s.empty()){ 
    struct node* top=s.top(); 
    visited[top->data]=true; 

    if(top->left!=NULL&&visited[top->left->data]==false) 
    printpath(top->left); 
    else if(top->right!=NULL&&visited[top->right->data]==false) 
    printpath(top->right); 
    else if(top->left==NULL&&top->right==NULL){ 
    print(); 
    cout<<"\n";  
    } 

    s.pop(); 
    } 

} 


int main() { 
    struct node* root = createNode(50); 
    root->left = createNode(7); 
    root->right = createNode(2); 

    root->right->left = createNode(1); 
    root->right->right = createNode(30); 
    root->right->right->right = createNode(40); 
    root->right->left->left = createNode(10); 
    root->right->left->left->left = createNode(12); 

    intilize(); 
    printpath(root); 

    return 0; 
}

該代碼給出了分段錯誤，因爲終止條件存在一些問題。有人可以幫我解決問題。

來源

2015-07-02 Ruthwik

該方法過於複雜且易碎。

爲此，不需要單獨的堆棧。

單獨的「可見」數組對此不需要。

所有需要的是遞歸訪問這個樹的股票遞歸訪問者，它還將一個附加參數添加到動態構建在堆棧上的結構中，該結構使用鏈接列表快速構建到根的路徑這是這樣的：

struct path_to_root { 
    struct path_to_root *next; 
    struct node *n; 
};

現在，所有需要打印到每片葉子音符的路徑是一個沼澤標準遊客，在樹遞歸迭代，而這個附加參數。這裏的一般方法的一個粗略的想法：

void printpath(struct node *n, struct path_to_root *p) 
{ 
    struct path_to_root pnext; 

    if (!n) 
     return; 

    if (!n->left && !n->right) 
    { 
     /* Your homework assignment here is to print the path that's in "p" */ 
    } 

    pnext.n=n; 
    pnext.next=p; 

    printpath(n->left, &pnext); 
    printpath(n->right, &pnext); 
}

，這將被調用爲：

printpath(root, NULL);

你的家庭作業，如上所述，是實現打印到葉的路徑的實際代碼，在指定的空間使用參數p。此時，葉子的路徑將在參數p中找到。

現在，這裏一個棘手的部分是，p將是葉的父母，p->next將是它的祖父母，等等。所以路徑從底部到頂部，而不是從頂部到底部，但這是一個小的細節，可以在打印代碼中處理。

或者，以相同的方式從上到下動態構建葉子的路徑不會有太多的額外工作。

來源

2015-07-02 12:23:09

將所有根打印到葉子路徑

回答

相關問題