反復単一スタックの実装バイナリツリーコピー関数

Question

考えられる練習として、繰り返しツリー（バイナリまたはバイナリ検索ツリー）のコピー機能を実装しようとしています。

それはそれは自明達成することができることが私の理解です：

• シングルスタック
• でラッパーを使用せずに（つまり、コピーし、元のノードへの参照を含む）
• 有するノードなしその親への参照（ノード内の親参照は、ツリーの真の定義に反するでしょうか？）

私は異なる実装を書いています上記の制約の逆数を満たす方程式ですが、制約を使って問題に近づける方法は不明です。

私はアルゴリズム4/eで何も見たことがなく、オンラインで何も見たことがありませんでした。私は現在の/以前のvarの順序とポストオーダーのコンセプトを使用することを検討しましたが、スタックをポップするときに正確に追跡する方法はありませんでした。私はハッシュマップについても簡単に考えましたが、余分なスタックのような余分なストレージだと思います。

私が見ていないアプローチの背後にある概念/イディオムを理解する助けがありがとうございます。

ありがとうございます。

編集：私がこれまで試した何のためのいくつかの要求

。ここで私は2スタックの解決策は、私は1スタックに最も自明に回ることができると思われると考えています。

これはC++で書かれています。私はC++ Primer 5/e（Lippman、Lajole、Moo）[C++ 11]とインターネットを使って、言語に慣れていません（プログラミングではない）。言語の観点からのコードのいずれかが間違っている場合は、私に知らせてください（私はコードレビュースタックエクスチェンジが実際のレビューの場所であると認識していますが）。

私は、コードの他の部分で使用されるテンプレートNodeを持っています。

template<typename T> 
struct Node; 

typedef Node<std::string> tree_node; 
typedef std::shared_ptr<tree_node> shared_ptr_node; 

template<typename T> 
struct Node final { 

public: 
    const T value; 
    const shared_ptr_node &left = m_left; 
    const shared_ptr_node &right = m_right; 

    Node(const T value, const shared_ptr_node left = nullptr, const shared_ptr_node right = nullptr) : value(value), m_left(left), m_right (right) {} 

    void updateLeft(const shared_ptr_node node) { 
     m_left = node; 
    } 

    void updateRight(const shared_ptr_node node) { 
     m_right = node; 
    } 

private: 
    shared_ptr_node m_left; 
    shared_ptr_node m_right; 
}; 

そして2つのスタックの実装。

shared_ptr_node iterativeCopy2Stacks(const shared_ptr_node &node) { 

    const shared_ptr_node newRoot = std::make_shared<tree_node>(node->value); 

    std::stack<const shared_ptr_node> s; 
    s.push(node); 

    std::stack<const shared_ptr_node> copyS; 
    copyS.push(newRoot); 

    shared_ptr_node original = nullptr; 
    shared_ptr_node copy = nullptr; 

    while (!s.empty()) { 

     original = s.top(); 
     s.pop(); 

     copy = copyS.top(); 
     copyS.pop(); 

     if (original->right) { 
      s.push(original->right); 

      copy->updateRight(std::make_shared<tree_node>(original->right->value)); 
      copyS.push(copy->right); 
     } 

     if (original->left) { 
      s.push(original->left); 

      copy->updateLeft(std::make_shared<tree_node>(original->left->value)); 
      copyS.push(copy->left); 
     } 
    } 

    return newRoot; 
} 

Answer 1

あなたは擬似コードで解決する必要がありますので、私は、C++用に堪能ではないよ：

node copy(treenode n): 
    if n == null 
     return null 

    node tmp = clone(n) //no deep clone!!! 

    stack s 
    s.push(tmp) 

    while !s.empty(): 
     node n = s.pop() 

     if n.left != null: 
      n.left = clone(n.left) 
      s.push(n.left) 
     if n.right != null: 
      n.right = clone(n.right) 
      s.push(n.right) 

    return tmp 

注意をclone(node)が深いクローンではないこと。基本的なアイデアは、ルートの浅いクローンから始め、そのノードのすべての子を繰り返して、それらのノード（元のノードへの依然として参照）を浅いコピーで置き換え、それらのノードの子などを置き換えることです。ツリーはDFS方式で表示されます。あなたがBFSを好む場合（何らかの理由で）、スタックをキューで置き換えることができます。このコードのもう1つの利点は、任意のツリーに対して少しの変更を加えて変更することができます。

このアルゴリズムの再帰バージョン（場合には、あなたが私の恐ろしいPROSA以上の再帰コードを好む）：

node copyRec(node n): 
    if n.left != null: 
     n.left = clone(n.left) 
     copyRec(n.left) 

    if n.right != null: 
     n.right = clone(n.right) 
     copyRec(n.right) 

    return n 

node copy(node n): 
    return copyRec(clone(n)) 

EDIT：あなたが作業したコードを見てしたい場合は
、私が作成しましたPythonでimplementation