如何高效地從特定節點產生二叉樹？

不知道這是一個正確的地方要問這樣的問題。但我只是將它張貼反正...如何高效地從特定節點產生二叉樹？

假設我有一個二叉樹，其中某些節點標記爲red：

 n1 
    /\ 
    red n2 
/\ \ 
    n3 n4 red 
     /\ 
     n5 n6

所以我想要做的，是每個red節點，產生樹成兩棵新的樹，並把每個孩子成一棵樹。

因此，對於上述情況下，它會成爲四棵樹是這樣的：

n1 
/\ 
n3 n2 
    /
    n5 

    n1 
/\ 
n4 n2 
    /
    n5 

    n1 
/\ 
n3 n2 
    \ 
    n6 

    n1 
/\ 
n4 n2 
    \ 
    n6

這似乎是一個很乾淨定義的問題..但到目前爲止，我只是不能想出了一個很好的解決方案。

任何人都可以在這個問題上解決一些問題嗎？萬分感謝！

來源

2017-04-08 computereasy

做一元的brances，例如'n5'或'n6'必須特別是左右分支，否則它們可以是？它也必須表示爲樹或可以用'（）'表示。如果是，則轉換爲BNF並生成所有的模式，例如'S = A n1（n2 B）。 A = n3 | N4。 B = n5 | n6.' –

謝謝@GuyCoder，'n5'和'n6'不一定要在特定的左側和右側。另一方面，我發現我很難明白你的觀點。無論如何，你能否詳細闡述它..？謝謝！ – computereasy

的實地觀測，可導致一個乾淨的實現：

如果有n紅色節點，那麼將有2個^ñ樹（這忽略其中紅色節點是葉的情況 - - 這些可能不重要，可以通過預處理步驟消除）。
0和2 ^Ñ之間的任何數k - 1可以表示一個配置 - 在第i個^紅色節點（即是否保留向左或右子樹）的決定被指示由^第位k。該位可以使用逐位操作，例如等來容易地獲得。用0

比較k & (1 << i)可以由一個生成樹一個主要功能是這樣的：

void spawnAllTrees(baseTree) { 
    int nRed = countRedNodes(baseTree); 

    // this assigns to each red node an index between 0 and nRed - 1 
    // (e.g. according to a pre-order tree traversal). 
    // it computes a hash map denoted as "redIndex" which 
    // stores the mapping from Node to int 
    computeRedIndices(baseTree); 

    for (int k = 0; k < (1 << nRed); k++) { 
     crtTree = spawnTree(baseTree, k); 
    } 
}

爲spawnTree的代碼將是：

Node spawnTree(baseTreeNode, k) { 
    if (baseTreeNode.isRed()) { 
     idx = redIndex[baseTreeNode]; 
     if (!bitIsSet(k, idx)) { 
      return spawnTree(baseTreeNode->left(), k); 
     } else { 
      return spawnTree(baseTreeNode->right(), k); 
    } else { 
     return new Node(baseTreeNode->value(), 
         spawnTree(baseTreeNode->left(), k), 
         spawnTree(baseTreeNode->right(), k)); 
    } 
}

編輯：

更改字母有點 - 增加一個計數器來確定當前的紅色節點索引是無效的。在某個紅色節點的不同決策可能會使另一個紅色節點接收不同配置的不同索引。

來源

2017-04-08 18:00:09 qwertyman

太棒了。我沒有嘗試過這種方法，但這看起來正確和優雅。非常感謝你提供這個有價值的解決方案！ – computereasy

謝謝您的讚賞！不幸的是，最初的版本存在一個問題，現在已經修復，但失去了一點優雅。 :) – qwertyman

這裏的算法：

node main_root_address; //address of very first node 

function myfunc_inorder(root_address) //call this from main 
{ 
    if root_address is null return; 

    myfunc_inorder(root_address->left); 

    if(root_address->value is "red") 
    { 
    node temp = root_address; 
    root_previous->parent = root_address->left; 
    //inside each node along with value and pointer to left and right    subtree store the address of the parent node. 
    myfunc_inorder(main_root_address); 
    root_previous->parent = root_address->right; 
    myfunc_inorder(main_root_address); 
    root_address = temp; 
    } 

    myfunc_inorder(root_address->right); 
}

如何該算法的工作？

首先，我將與「節點N1」開始，然後移動到「紅點」再到「節點N3」再回到「紅點」 ......在這裏，我將取代「紅」與左子樹然後用合適的子樹，直到沒有紅色留下重複算法...

來源

2017-04-08 16:24:30 Arvindsinc2

由於二叉樹可以被表示爲線性表達式二進制樹

n1 
/\ 
red n2 
/\ \ 
n3 n4 red 
    /\ 
     n5 n6

可以表示爲線性表達式((n3 red n4) n1 (n2 (n5 red n6)))

現在線性前PRESSION爲二進制樹可以表示爲一個BNF和red可與|或操作者更換

<s> ::= <a> n1 (n2 <b>) 
<a> ::= n3 | n4 
<b> ::= n5 | n6

現在，所有可能的組合（行走）本BNF是

n3 n1 (n2 n5) 
n3 n1 (n2 n6) 
n4 n1 (n2 n5) 
n4 n1 (n2 n6)

並且這些可以被轉回到你答案的樹上。

來源

2017-04-08 17:13:49

如何高效地從特定節點產生二叉樹？

回答

相關問題