c++ - バイナリ ツリーと特別なノードの印刷

Question

バイナリ表現でこのようなツリーがあります。

                 1
                /
               2
                \
                 3
                / \
               6   4
                \   \
                 7   5
                    /
                   8
                  /
                 9
                  \
                   10
                     \
                      11

しかし、実際にはこれは二分木ではなく、

     1
  / | | \
 2  3 4 5
    /\  |
    6 7 8
       /| \
      9 10 11

次のようなものを印刷するのを手伝ってもらえますか（子供は逆の順序で印刷されます）

1 : 5 4 3 2
5 : 8
3 : 7 6
8 : 11 10 9

私の TNode クラスは次のようになります。

class TNode {
public:
    unsigned long int data;
    TNode * left;///first child
    TNode * right;/// sibling
    TNode * parent;/// parent

    TNode(unsigned long int d = 0, TNode * p = NULL, TNode * n = NULL)///konstruktors
    {
        left = NULL;
        right = NULL;
        parent = p;
        data = d;
    }
};

これにはスタックの実装が必要ですか?

Answer 1

私はこのようなものを作りましたが、whileループのために再帰的ではありません。それをよりrecにする方法はありますか

void mirrorChilds(TNode * root)//
{
    if(!root) return;
    cout << root->data << " ";
    //tmp = tmp->right;
    if(!root->left) return;
    TNode * tmp = root->left;
    while(tmp != NULL)
    {

        root->left = tmp;
        tmp = tmp->right;
    }

   tmp = root->left;
   while(root != tmp)
    {
        cout << tmp->data << " ";
        tmp = tmp->parent;

    }
    cout << endl;
    tmp = root->left;
    while(root != tmp)
    {
        if(tmp->left) mirrorChilds(tmp);
        //if(tmp->left) cout << tmp->left->data << endl;
        tmp = tmp->parent;

    }
}

それは完全に正常に動作しますが、私は O(n*log(n)) 時間を取得しようとしています...