如何高效地从特定节点产生二叉树？

不知道这是一个正确的地方要问这样的问题。但我只是将它张贴反正...如何高效地从特定节点产生二叉树？

假设我有一个二叉树，其中某些节点标记为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

如何高效地从特定节点产生二叉树？

回答

相关问题