如何遞歸地訪問所有的樹節點

Question

所以，我喜歡這個

     a 
        /\ 
         b  c 
        /\ /
        d e f 

功能的樹必須打印：

a 
ab 
abd 
abe 
ac 
acf 

我的老師說，我可以有唯一的參數是一個指向第一個節點的指針。我不能使用任何其他變量，包括靜態變量和全局變量。

void print(Node* a) 
{ 
    if(a==NULL){return;} 
    cout<<a->data; 
    if(a->left!=NULL){print(a->left);} 
    if(a->right!=NULL){print(a-right);} 
} 

到目前爲止，我的程序只能打印「abdecf」。任何建議？

Answer 1

您可以將代表父節點添加到表示節點的結構中。像這樣 -

class Node { 
public: 
    char data; 
    Node *left; 
    Node *right; 
    Node *parent; 
}; 

所以用這個修改的數據結構，現在，你將打印在每個級別的路徑從當前節點到根，像這樣 -

void print(Node* a) 
{ 
    Node *cur = a; 
    do { 
    cout << cur->data << ", "; 
    cur = cur->parent; 
    } while(cur != NULL); 
    if(a->left != NULL){ 
    print(a->left); 
    } 
    if(a->right != NULL){ 
    print(a->right); 
    } 
}