如何有效地从某些节点生成二叉树？

Question

不确定问这样的问题是否合适..但我还是会post...

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

这似乎是一个非常明确的问题..但到目前为止我还想不出一个好的解决方案..

任何人都可以阐明这个问题吗？非常感谢！

Answer 1

算法如下：

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);
}

这个算法是如何工作的？

首先我将从 "node n1" 开始，然后移动到 "node red" 然后移动到 "node n3" 然后回到 "node red"...在这里我将替换 "red" 用左子树然后用右子树重复算法直到没有红色留下...

Answer 2

由于二叉树可以表示为线性表达式，因此二叉树

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

可以表示为线性表达式((n3 red n4) n1 (n2 (n5 red n6)))

现在，二叉树的线性表达式可以表示为 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)

这些可以重新变成你的答案树。

Answer 3

一些可以导致干净实施的观察结果：

如果有n个红色节点，那么就会有2ⁿ棵树（这忽略了红色节点是叶子的情况——那些可能没有这无关紧要，可以通过预处理步骤消除）。
0 到 2ⁿ 之间的任何数字 k - 1 可以代表一种配置——第 i^{th[=36 次做出的决定=]红色节点（即是否保留左子树或右子树）由[=13=的第i^th位表示].可以使用按位运算轻松获得此位，例如通过比较 k & (1 << i) 和 0.}

可以一棵一棵地生成树的主要函数如下所示：

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));
    }
}

编辑:

稍微更改了算法 -- 递增计数器以确定当前的红色节点索引无效。某个红色节点的不同决策可能会使另一个红色节点针对不同的配置接收不同的索引。

如何有效地从某些节点生成二叉树？

How to efficiently spawn a binary tree from certain nodes?

algorithm

tree

binary-tree

graph-algorithm

binary-search-tree