Java非二叉树前序遍历

Question

我在遍历非二叉树并输出前序枚举时遇到一些问题。

我当前的代码是:

  public String GetPreOrder(ADS2TreeNode root, String res)
  {        
      res += data;
      if (numberOfChildren != 0)
      {
          for (int i = 0; i < numberOfChildren; i++)
          {
              res += "," + children[i];
          }            
      }      
   return res;              
  }


  public String GetPreOrder()
  {  
      String res = "";
      return root.GetPreOrder(root, res);
  }

基于“(B(E(K),F))”的测试数据它输出 B,E(K),F但是它应该输出 B、E、K、F

我相信这是因为它只是打印存储 E 子代的数组而不是单独访问它们？但是我不确定如何做到这一点。

有人能解释一下为什么会发生这种情况以及如何解决这个问题吗？

#

我现在遇到以下代码问题:

 public String GetPreOrder(ADS2TreeNode root, String res)
  {    
      if (root.numberOfChildren == 0)
      {
          res += root.data;
          root = root.parent;
      }
      else
      {


      for (int i = 0; i < root.numberOfChildren; i++)
          {
              res += root.data + ',';
              root = root.getChild(i);
              res = GetPreOrder(root, res);
          }

       }          
        return res;     
  }

在调试它时，它会按应有的方式循环遍历每个子树，但是它并没有完全到达树的末尾 - 我花了很长时间试图通过调试找出它，但我似乎无法理解为什么.

任何人都可以看到我的代码中的错误或我缺少的内容吗？

Answer 1

假设有一个函数pre-order-traversal(tree)，它会执行以下操作:

1. 访问根并显示其值/内容等。
2. 通过递归调用 pre-order-traversal(tree) 函数来访问第一个子树。
3. 通过递归调用 pre-order-traversal(tree) 继续从左到右处理所有其他子树。

您的代码不会遍历子树，而仅(隐式)调用其 toString() 方法，该方法显示给定的子树及其在括号中的子树。

因此，解决方案是对子级递归调用 GetPreOrder(...)，因为它们也是树。

出现第二个问题是因为您将 root 重置为第一个 child 。因此，在 for 循环的第二次迭代中，不使用真正的根，而是使用第一个子树的根。只需不要重复使用参数 root 并使用局部变量即可。

res += root.data + ',';
for (int i = 0; i < numberOfChildren; i++)
{
    ADS2TreeNode child = root.getChild(i);
    res += GetPreOrder(child, res);
}

如果您能够以某种方式从问题的第一部分访问数组，则可以使用更好的 for-each-loop。

res += root.data + ',';
for(ADS2TreeNode child : children) {
    res += GetPreOrder(child, res);
}