Java二叉搜索树-递归Void复制方法

Question

我需要从头开始为二叉搜索树创建一个递归复制方法。该方法应该将给定BinarySearchTree对象中的每个项复制到调用BinarySearchTree对象中。唯一的问题是该方法必须是void，并且我在此主题上查找的所有内容似乎都使用不同的返回类型来完成此操作。

我真的不知道如何从这样的东西开始，我所拥有的只是方法的空外壳和它的包装器。我不确定私有方法中的参数是否正确，但这是我最好的猜测。

public void copy(BinarySearchTree<E> bst2){
        copy(bst2, root, bst2.root);
    }
private void copy(BinarySearchTree<E> bst2, Node node1, Node node2){
    }

我很感激所有的帮助。

谢谢!

Answer 1

立即想到的是(前面是粗略的伪代码):

class Tree {
     //stuff in the tree with a root node, etc...
     copyTree(Node parentTreeNode, Node copyTreeNode) {
          if(copyTreeNode == null)
              return;
          parentTreeNode = clone(copyTreeNode) //clone just copies the node's values into the node.
          if(copyTreeNode.leftChild != null) {
              parentTreeNode.leftChild = new Node();
              copyTree(parentTreeNode.leftChild, copyTreeNode.leftChild);
          }
          if(copyTreeNode.rightChild != null) {
              parentTreeNode.rightChild = new Node();
              copyTree(parentTreeNode.rightChild, copyTreeNode.rightChild);
          }
     }
}

你可以用两个根节点调用它，让它递归，它会为你构建树。

因此，如果基本情况被触发(当前节点为空)，那么您通过返回跳过该节点并继续递归过程(基本情况在递归技术中很重要，否则您将得到无限递归)。因此，我们从根节点开始，复制它(如果它不为空)，然后移动到左子树，假设它也不为空。我们在这个方法中暂停，调用子树上的方法，它在那里"暂停"，并在左边造成....当它一路向下返回时，它"暂停"的每个位置都会恢复，以相同的过程移动到每个节点上的右子节点。一旦左子树递归到它自己，我们继续在顶部节点，并移动到右子树，在那里做同样的事情(就像在所有子节点中递归地做的那样)。当一切完成后，它就会正常返回。

递归并不是特别难，但一开始需要一些练习才能理解。

这是一个粗略的想法，还没有经过测试，但这大致是我的做法。可能值得注意的是，如果主树中已经有数据，或者您提交了根节点以外的节点，那么这种处理方式不能保证树是相同的。但是在该节点下的值是一样的