二叉树，返回预先遍历中的下一个节点

Question

我有一个任务，我需要一些方法的帮助。

所以我有这样的树：

   A 
      / \ 
      B  C 
     / \/ \ 
      D E F  G 
     / \ 
     H  I 
    / \ 
    J  K 

，我的方法是：

public BinaryTree preorderNext(BinaryTree t, BinaryTree v, BinaryTree prev) {  

    prev = t; 

    if(t.getLeft() != null) { 
     preorderNext(t.getLeft(), v, prev); 
    } 

    if(t.getRight() != null) { 
     preorderNext(t.getRight(), v, prev); 
    } 


    if(prev == v) { 
     return t; 
    } 

    return null; 
} 

讲师给了一个简单的实现树。这个类被称为BinaryTree，如果你想建立一个到它的节点链接，那么你可以指定左边和右边的BinaryTree节点是什么。

一个节点有两个链接（一个到左边，另一个到右边的孩子），没有链接到头部。

因此，使用当前的方法，我能够成功地进行预遍历，我通过编写存储在节点的元素的打印语句来测试。

但是当我运行测试时，它告诉我A的下一个前序节点是B，K的下一个前序节点会抛出一个空异常，但它应该是I？

任何想法，我哪里去错了？变量prev应该保存对访问的最后一个节点的引用，所以如果它等于节点v（这是我指定的节点，在v之后返回节点），我不应该得到下一个节点吗？

Answer 1

这里是preorder traversal递归完成的实现。

public void preOrderTraversal(BinaryTree root){ 
    if(root == null) return; 

    System.out.println(root); 
    preOrderTraversal(root.getLeft()); 
    preOrderTraversal(root.getRight()); 
} 

注：

1. 我不知道你的做法;你为什么要返回一个节点？在任何情况下，当root为空时，您可以返回“emptyNode”并通过if语句处理它。
2. 正如你所看到的，我只处理root，任何级别的root变化。试着用一个run-through来想象这个，你会理解这个概念。
3. 您在开始时缺少对空节点的检查（特别是对于t）。

您可以继续调整您的结果。

最后要说的是这种方法的运行时复杂性，我强烈建议理解递归函数的运行时复杂性。它将在未来帮助你很多。检查this wikipedia article重现关系。

Answer 2

我不确定递归执行该任务是否容易。

解决任务使用堆栈可能是一个更好的方法迭代方式：

public BinaryTree preOrderNext(BinaryTree toSearch) { 

    Stack<BinaryTree> openList = new Stack<BinaryTree>(); 

    openList.push(root); 

    while (openList.empty() == false) { 
     BinaryTree curr = openList.pop(); 

     if (curr.getRight() != null) 
      openList.push(curr.getRight()); 

     if (curr.getLeft() != null) 
      openList.push(curr.getLeft()); 

     if (curr.equals(toSearch) && openList.empty() == false){ 
      return openList.pop(); 
     } 
    } 
    return null; 
} 

，此方法是测试，但应该工作。

Answer 3

我提供了一个运行在O(h)运行时间的答案。

class Node { 
    public int key; 
    public Node l; 
    public Node r; 
    public Node p; 

    public Node(int key) { 
     this.key = key; 
     this.l = null; 
     this.r = null; 
     this.p = null; 
    } 
} 

public Node preorderNext(Node v) { 
    if (v.l != null) { 
     return v.l; 
    } else if (v.r != null) { 
     return v.r; 
    } else { 
     while (v.p != null) { 
      if (v == v.p.l) { 
       if (v.p.r != null) { 
        return v.p.r; 
       } else { 
        v = v.p; 
       } 
      } else { 
       if (v.p.p == null) { 
        return null; 
       } else if (v.p == v.p.p.l) { 
        if (v.p.p.r != null) { 
         return v.p.p.r; 
        } else { 
         v = v.p; 
        } 
       } else { 
        v = v.p; 
       } 
      } 
     } 
     return null; 
    } 
}