Java解析二叉树结构

Question

我目前正在研究一些数据结构，并且遇到了一些存储在二叉树中的数据，但我不完全确定解析它的最佳方法。

数据基本上是这样存储的:

Structure 1: 
  LeftChild: 0xaddress
    Structure 2: 
      LeftChild: 0xaddress
        Structure 3:
         LeftChild: 0xaddress
          ........
         RightChild: 0xaddress
          Structure 4:
            LeftChild: 0xaddress
            RightChild: 0xaddress
      RightChild: 0xaddress
  RightChild: 0xaddress

现在显然很难对二叉树进行文本解释，所以希望我上面的糟糕尝试能稍微解释一下。本质上，这一切都是从一个结构开始的，该结构有左树条目和右树条目，每个树条目又都有左树条目和右树条目，最终其中一个将耗尽节点，然后树的下一个分支继续。

我不完全确定解决这个问题的最佳方法。

我的第一个想法是通过使用 while 循环来继续追踪树节点，但这似乎有点令人头痛。

我知道 Java 有二叉树实现，但我不知道是否可以将它们用于此类工作。我从未尝试过使用它们，所以我可能是错的。

如果有人对如何解决这个问题有任何意见或建议，我将不胜感激。

谢谢!

Answer 1

一个建议:如果你的树太深，你应该避免基于递归的解决方案。那是因为你可能会遇到堆栈溢出问题。

为了处理这种情况，您可以使用堆栈。

以下伪代码无需递归即可遍历所有二叉树节点。

visitNodes(root) 
    add the root on the stack

    while the stack is not empty
        nodeToBeProcessed <- pop the top node from the stack

        process nodeToBeProcessed

        if nodeToBeProcessed has a left child
            add the left child on the stack

        if nodeToBeprocessed has a right child
            add the right child on the stack

注意:pop 操作返回并从堆栈中删除顶部节点。

注 2:如果深度不是问题，基于递归的解决方案通常会更简单。