2

我正在阅读的一篇论文声称

很容易看出有一个线性时间算法来计算函数l()

wherel()给出最左边的孩子（输入和输出都在树的后序遍历中）。但是，我只能想到一个幼稚的O(n^2)实现，n树中的节点数是多少。

例如，考虑以下树：

  a
 / \
c   b

在后序遍历中，树是c b a。相应的函数l()应该给出c b c。

这是我O(n^2)及时的实现。

public Object[] computeFunctionL(){
    ArrayList<String> l= new ArrayList<String>();
    l= l(this, l);
    return l.toArray();
}

private ArrayList<String> l(Node currentRoot, ArrayList<String> l){
    for (int i= 0; i < currentRoot.children.size(); i++){
        l= l(currentRoot.children.get(i), l);
    }
    while(currentRoot.children.size() != 0){
        currentRoot= currentRoot.children.get(0);
    }
    l.add(currentRoot.label);
    return l;
}

树是这样制作的：

public class Node {
private String label;
private ArrayList<Node> children= new ArrayList<Node>();
...
4

3 回答 3

1

您可以l()在不到 O(n^2) 的时间内找到整棵树。这个想法是按顺序遍历树，在遍历左分支时维护您访问过的节点堆栈。当你到达一个叶子时，那是整个分支的最左边的节点。

这是一个例子：

class BTreeNode
{
    public readonly int Value;
    public BTreeNode LeftChild { get; private set; }
    public BTreeNode RightChild { get; private set; }
}

void ShowLeftmost(BTreeNode node, Stack<int> stack)
{
    if (node.LeftChild == null)
    {
        // this is the leftmost node of every node on the stack
        while (stack.Count > 0)
        {
            var v = stack.Pop();
            Console.WriteLine("Leftmost node of {0} is {1}", v, node.Value);
        }
    }
    else
    {
        // push this value onto the stack so that
        // we can add its leftmost node when we find it.
        stack.Push(node.Value);
        ShowLeftmost(node.LeftChild, stack);
    }
    if (node.RightChild != null)
        ShowLeftmost(node.RightChild, stack);
}

复杂度显然不是 O(n^2)。相反，它是 O(n)。

遍历树需要 O(n)。没有节点被多次放置在堆栈上。该算法的最坏情况是包含所有左节点的树。在这种情况下，遍历树是 O(n)，枚举堆栈是 O(n)。最好的情况是一棵包含所有正确节点的树，在这种情况下，永远没有要枚举的堆栈。

所以 O(n) 时间复杂度，O(n) 最坏情况下的堆栈额外空间。

于 2013-11-08T20:32:45.737 回答
1

您可以使用一种简单的递归算法，可以在每个节点的 O(1) 时间内计算此信息。由于总共有 n 个节点，因此这将在 O(n) 总时间内运行。

基本思想是以下递归见解：

  • 对于没有左孩子的任何节点 n，l(n) = n。
  • 否则，如果 n 有左子 L，则 l(n) = l(L)。

这就产生了这种递归算法，它用它的 l 值注释每个节点：

function computeL(node n) {
   if n is null, return.

   computeL(n.left)
   computeL(n.right)

   if n has no left child:
      set n.l = n
   else
      set n.l = n.left.l

希望这可以帮助！

于 2013-11-08T23:49:59.297 回答
0

请看第 3.1 节：

3.1。符号。根据从左到右的后序编号，令 T[i] 为树中的第 i 个节点，l(i) 为以 T[i] 为根的子树的最左叶后代的编号。

鉴于关于符号的那句话，我假设函数 l() 指的是在线性时间内找到单个节点。

可能有一种更优雅（比 O(n^2) 更好）的方式来查找整个树的 l()，但我认为它指的是单个节点。

于 2013-11-08T18:26:31.053 回答