作业：二叉树 - 层序遍历[已关闭]

Question

有没有办法从最低层到高层（根）访问二叉树？

不是从根到最底层！！！

（并且不使用层序遍历和堆栈......！！！）<--- its opposite..

好难...谢谢！

---

我以更好的方式解释。我有一个代数表达式树（所以不平衡）。我必须使用队列（并且仅使用队列）对其进行评估。我问这个问题是因为我认为唯一的方法是从最低级别开始获取节点，直到根......

示例： 树 ( + ( * ( 2 ) ( 2 ) ) ( 3 ) )

我排队：

入队（1）； 入队（2）；

(*) -----> 出队；出队；结果 = 2 * 2；入队（结果）； 入队3； (+) -----> 出队；出队；结果 = 4 + 3；给出结果；

所以我需要进行这样的遍历：2； 2 ; *; 3 ; +

不知道说清楚了没有……

Answer 1

这里存在一些挑战，导致不同的解决方案：

1. 你能爬上树吗？通常数据结构是这样设置的，所以你只能往下走。可以找到所有叶子节点，逐级放入优先级队列，然后向上遍历。

2. 你能存储 O(n) 的额外数据吗？您可以以正常的广度优先方式遍历它，按级别将指针插入到优先级队列中，就像前面的解决方案一样，但这次在初始遍历期间插入所有节点。但这将增加遍历期间使用的辅助数据的最大大小。

3. 树是否保证平衡且完整，就像在堆状树中一样？如果是，您可以通过更简单的方式遍历它，只需前往正确的位置即可。

Answer 2

你可能可以轻松做到这一点如果你维护了一个指向最大深度节点的指针。如果不这样做，那么您必须在开始遍历之前找到该节点。此外，您的节点都必须有指向其父节点的指针。

Answer 3

假设我正确理解了你的问题：如果你想遍历树，首先访问 a 叶子，最后访问根，则可以在遍历树时访问返回途中的节点。

function traverse(node)
    for each child of node
        traverse(child)
    end
    visit(node)
end

如果您想按级别顺序访问节点，您可以执行类似的操作（尽管使用堆栈 - 我不确定您是否根本不需要一个堆栈或使用堆栈的某些特定解决方案）：

queue.push(root)
while queue is not empty
    node = queue.pop()
    for each child of node
        queue.push(child)
        stack.push(child)
    end
end
while stack is not empty
    visit(stack.pop())
end

您可以仅使用队列来完成此操作，但时间复杂度会更差，如果您这样做：

for i = treedepth down to 0
    queue.push(root)
    while queue is not empty
        node = queue.pop()
        if node has depth i
            visit(node)
        else
            for each child of node
                queue.push(child)
            end
        end
    end
end

如果需要，可以使用初始遍历找到树深度和节点级别。

但是，如果允许进行递归调用，则实际上可以访问堆栈（调用堆栈）。可以利用这来实现第二个解决方案，但使堆栈隐式。

function unwind(queue)
    if queue is not empty
        node = queue.pop()
        unwind(queue)
        visit(node)
    end
end

queue.push(root)
while queue is not empty
    node = queue.pop()
    for each child of node
        queue.push(child)
        queue2.push(child)
    end
end

unwind(queue2)

当然，如果您可以访问几乎任何其他数据结构（列表、数组、优先级队列、双端队列等），您可以轻松地自己实现堆栈。但那么一开始就禁止堆栈就毫无意义了。

Answer 4

队列仅适用于从树的根到叶遍历级别顺序。

您可以使用深度优先遍历来打印特定级别。 像这样：

 void printLevel(BinaryTree *p, int level) {
   if (!p) return;
   if (level == 1) {
     cout << p->data << " ";
   } else {
     printLevel(p->left, level-1);
     printLevel(p->right, level-1);
   }
 }

要打印从叶到根的所有级别，您需要找到树的最大深度。这也可以使用深度优先遍历轻松完成（您可以轻松地通过谷歌搜索解决方案）。

void printLevelOrder(BinaryTree *root) {
  int height = maxHeight(root);
  for (int level = height; level >= 1; level--) {
    printLevel(root, level);
    cout << endl;
  }
}

运行时间复杂度令人惊讶，为 O(N)，其中 N 是节点总数。

更多信息和运行时复杂度分析，请参考以下页面：

http://www.ihas1337code.com/2010/09/binary-tree-level-order-traversal-using_17.html