作业：二叉树 - 水平顺序traversversal

Question

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

不是从根级到最低级!!!

（而不是使用水平序遍历和堆栈... !!!）< ---它的反面..

这么难...谢谢！

Answer 1

提供我正确理解你的问题：如果你想遍历树首先访问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 2

你可能很容易做到这一点如果你维护了一个指向最深处节点的指针。如果你不这样做，那么你必须在开始遍历之前找到该节点。此外，你的节点都必须有指向父母的指针。

Answer 3

这里有导致不同的解决方案的几个挑战：

1. 可以遍历了树？通常情况下，数据结构是建立起来的，所以你只能停下来。您可以找到所有叶节点，将它们按级别放入优先级队列中，然后遍历。

2. 您可以存储O（n）个附加数据吗？您可以按照普通的宽度优先方式遍历它，像先前的解决方案一样，将指针插入优先级队列中，但这次是在初始遍历期间插入所有节点。这将增加在遍历期间使用的辅助数据的最大大小。

3. 树是否保证平衡和充满，就像它可能在堆状树中一样？如果是这样，你可以通过简单的方式遍历它，只要去正确的地方。

Answer 4

我以更好的方式解释。我有一个代数表达式树（所以不平衡）。我必须使用一个队列（只有一个队列）来评估它。我问这个问题，因为我觉得唯一的办法是采取从最低级别开始节点，直到根...

例如： 树（+（*（2）（2））（3））

我排队和：

enqueue（1）; enqueue（2）;

（*）-----> dequeue;出队;结果= 2 * 2;入列（结果）; 入队3; （+）----->出队;出队;结果= 4 + 3;给出结果;

所以我需要有这个遍历：2; 2; *; 3; +

我不知道这是否是明确的......

Answer 5

队列只有从根遍历水平，以树的叶子非常有用。

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

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