c++ - すべてのツリーノードを再帰的に訪問する方法

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