0

我有一个关于将可能包含 null 的对象传递给其他方法的最佳方法的问题。如果传递的对象为空，则另一个方法将创建一个新实例。我的问题是如何允许第二种方法修改原始传递的空对象指针。基本上，我在从文件中读取 BST 并制作树时遇到了这个问题。我认为使用相同的示例解释问题更有意义：

在下面的代码中，我正在从存储在队列中的所有值读取和构建 BST。队列值是我从另一个方法读取的树的按顺序遍历。

    TreeNode root2;
public void readBST(Queue<Integer> input){
    if (input==null || input.isEmpty()) return;     
    int i=input.poll();
    root2 = new TreeNode(i);
    readBSTHelper(root2.leftChild , input, Integer.MIN_VALUE , i-1);
    readBSTHelper(root2.rightChild, input, i+1, Integer.MAX_VALUE);
}

private void readBSTHelper(TreeNode curr, Queue<Integer> input, int min, int max){
    if (input==null && input.isEmpty()) return;
    int i = input.peek();
    if (i>=min && i<=max){
        input.poll();
        curr = new TreeNode(i);
        readBSTHelper(curr.leftChild, input, min, i-1);
        readBSTHelper(curr.rightChild,input, i+1, max);
    }
}

但是，我面临的问题是，当root2创建时，它是leftChild并且rightChild是null。实际上TreeNode(i)使 a TreeNodewith data=iand leftChildand rightChildequal null。当我调用readBSTHelper传递时root2.leftChild，它传递一个null指针。由于它是一个null指针，因此将指针的副本null传递给readBSTHelper. 因此，来自 的结果readBSTHelper会丢失并且永远不会返回/分配给 real root2.leftChild。我们可以通过传递原始指针的引用来防止 C++ 中出现此类问题。我可以通过如下修改代码暂时解决问题：

    TreeNode root2;
public void readBST(Queue<Integer> input){
    if (input==null || input.isEmpty()) return;     
    int i=input.poll();
    root2 = new TreeNode(i);
    readBSTHelper(root2, "left", input, Integer.MIN_VALUE , i-1);
    readBSTHelper(root2, "right", input, i+1, Integer.MAX_VALUE);
}
private void readBSTHelper(TreeNode curr, String side, Queue<Integer> input, int min, int max){
    if (input.isEmpty()) return;
    int i = input.peek();
    if (i>=min && i<=max){
        input.poll();
        if (side.equals("left")) {
            curr.leftChild = new TreeNode(i);
            readBSTHelper(curr.leftChild,"left", input, min, i-1);
            readBSTHelper(curr.leftChild, "right", input, i+1, max);
        } else {
            curr.rightChild = new TreeNode(i);
            readBSTHelper(curr.rightChild,"left", input, min, i-1);
            readBSTHelper(curr.rightChild, "right", input, i+1, max);
        }

    }
}

但是这段代码在我看来很难看。关于如何使第一个代码工作的任何建议？

4

1 回答 1

2

选项 1：包装器

class NodeWrapper
{
  TreeNode node;
}

class TreeNode
{
  ...
  TreeNode(int num)
  {
    leftChild = new NodeWrapper();
    rightChild = new NodeWrapper();
    ...
  }
  NodeWrapper leftChild, rightChild;
}

void readBSTHelper(NodeWrapper curr, Queue<Integer> input, int min, int max)
{
  ...
}

选项 2：在构造函数中初始化子项

我建议有一个专门用于此目的的单独构造函数（不是如下所示），否则您的插入函数会错误地创建子代。

class TreeNode
{
  ...
  TreeNode()
  {
    val = null;
  }
  TreeNode(int num)
  {
    init(num);
  }
  init(int num)
  {
    leftChild = new TreeNode();
    rightChild = new TreeNode();
    val == num;
  }
  Integer val;
}

public void readBST(Queue<Integer> input){
    if (input==null || input.isEmpty()) return;     
    int i=input.poll();
    root2 = new TreeNode(i);
    if (!readBSTHelper(root2.leftChild , input, Integer.MIN_VALUE , i-1))
      root2.leftChild = null; // delete child if not populated
    if (!readBSTHelper(root2.rightChild, input, i+1, Integer.MAX_VALUE))
      root2.rightChild = null; // delete child if not populated
}

boolean readBSTHelper(TreeNode curr, Queue<Integer> input, int min, int max){
    if (input==null && input.isEmpty()) return false;
    int i = input.peek();
    if (i>=min && i<=max){
        input.poll();
        curr.init(i);
        if (!readBSTHelper(curr.leftChild, input, min, i-1))
          curr.leftChild = null;
        if (!readBSTHelper(curr.rightChild, input, i+1, max))
          curr.rightChild = null;
        return true;
    }
    return false;
}
于 2013-03-08T07:24:05.867 回答