クローン部分は

Question

私は、ノードオブジェクトのツリー構造を構築していますBFSを介して選択されたノードを見つけることができる：

root.bfs(function(node){ 
    console.log(node, node.selected); 
}); 

...選択されたすべての対応するpにマークすることも非常に簡単ですルートまでのノードをアレント：

var n = node; 
do { 
    n.selected = true; 
    n = n.parentNode; 
} while (n); 

は今、私が選択した葉と対応する親ノードと最初のツリー構造のクローンを作成する必要がありますが、私は彼らに新しい子ノードを再割り当てすることはできませんよそれぞれ新しい親。

JSON.stringify（）で試行すると、循環参照エラーが発生します。

最初のツリーのクローンを、選択されたリーフを持つブランチだけでどのように再構成できますか？

Answer 1

選択されていないリーフパスを除外するために既存のツリーをプルーニングできると仮定すると、dfsがそれを行います。

欠点が：

1. 既存のツリーは、
2. 剪定子供がまだnull値児アレイ内のエントリとして存在する修飾されています。

   Prune-UnSelected-Leaf(root) 
   
   if(root) == null return null 
   
   if(root.children.length == 0) //Check if node is a Leaf 
       if(root.selected) 
       return root // Keep this node 
       else 
       return null; // Ignore the node 
   bool AnyChildSelected = false 
   for(i : 1 to children.Length) 
       var childSelectedNode = Prune-UnSelected-Leaf(children[i]) 
       if(childSelectedNode) 
       AnyChildSelected = true 
       root.children[i] = childSelectedNode 
   
   if(AnyChildSelected == true || node.selected == true) // Keep the node 
       return node 
   else 
       return null; // Ignore the node 
   

   擬コード

O(1)削除をサポートするデータ構造を使用することにより、挿入

を克服できるようなものであったと仮定します。

 Root Node 
     / | \ 
    / |  \ 
    A(T) B(F) C(F) 
    /   / 
    D(F)   E(T) 

選択されていないパスがnullに設定されており、この

  Root Node 
     / X  \ 
Return A/ X(null) \ Return C 
     A(T) B(F) C(F) 
     X   / 
    X Return null/Return E 
    D(F)   E(T) 

のようになります。アルゴリズムを実行した後またずに、ツリーのクローンを作成するには、上記のアルゴリズムを変更することができます既存のツリーを変更します。 Clone-Node(node)ノードを取る関数であると、ノードに関連した情報とディープコピーを作成してみましょうが、parentに対して空/デフォルトの初期化を親に

addChild(child) 
    child.parent = this 
    l = this.children.push(child); 
    return this.children[l-1]; 

を既存の子ノードを追加するaddChildため

過負荷、 childrenおよびselected属性

Clone-Tree(root) 

if(root) == null return null 

if(root.children.length == 0) //Check if node is a Leaf 
    if(root.selected) 
    return Clone-Node(root) // Keep this node 
    else 
    return null; // Ignore the node 

bool AnyChildSelected = false 
parent = Clone-Node(root) 

for(i : 1 to children.Length) 
    var childSelectedNode = Clone-Tree(children[i]) 
    if(childSelectedNode != null) 
    AnyChildSelected = true 
    parent.AddChild(childSelectedNode) // Add child to new parent 

if(AnyChildSelected == true || root.selected == true) // Keep the node 
    return parent 
else 
    return null; // Ignore the node