如何递归地访问所有的树节点

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