java - 替换未排序树中的节点时无限循环

Question

我正在用 Java 做家庭作业，我必须用 String 作为数据值创建一个未排序的二叉树。然后，我必须编写一个函数，用包含新描述的新对象替换 Node 和任何与旧描述匹配的重复 Node。

这是我正在使用的代码，包括导致无限循环的测试用例:

public class Node {

 private String desc;
 private Node leftNode = null;
 private Node rightNode = null;
 private int height;

 public Node(String desc) {
   this.desc = desc;
   height = 0; // assumes that a leaf node has a height of 0
 }

 public String getDesc() {
  return desc;
 }

 public Node getLeftNode() {
  return leftNode;
 }

 public Node getRightNode() {
  return rightNode;
 }

 public void setLeftNode(Node node) {
   ++height;
   leftNode = node;
 }

 public void setRightNode(Node node) {
   ++height;
   rightNode = node;
 }

 public int getHeight() {
   return height;
 }

 public int addNode(Node node) {
   if(leftNode == null) {
     setLeftNode(node);
     return 1;
   }
   if(rightNode == null) {
     setRightNode(node);
     return 1;
   }
   if(leftNode.getHeight() <= rightNode.getHeight()) {
     leftNode.addNode(node);
     ++height;
   } else {
     rightNode.addNode(node);
     ++height;
   }
   return 0;
 }

 public static void displayTree(Node root) {
   if(root != null) {
     displayTree(root.getLeftNode());
     System.out.println(root.getDesc());
     displayTree(root.getRightNode());
   }
 }

 public static Node findNode(Node current, String desc) {
   Node result = null;
   if(current == null) {
     return null;
   }
   if(current.getDesc().equals(desc)) {
     return current;
   }
   if(current.getLeftNode() != null) {
     result = findNode(current.getLeftNode(), desc);
   }
   if(result == null) {
     result = findNode(current.getRightNode(), desc);
   }
   return result;
 }

 public static void replaceNode(Node root, String oldDesc, String newDesc) {
   if(oldDesc == null || newDesc == null) {
     System.out.println("Invalid string entered");
     return;
   }
   boolean replacedAllNodes = false;
   while(replacedAllNodes == false) {
     Node replace = findNode(root, oldDesc);
     if(replace == null) { // No more nodes to replace
       replacedAllNodes = true;
       return;
     }
     replace = new Node(newDesc);
     root.addNode(replace);
   }
   return;
 }


 public static void main(String[] args) {
     Node root = new Node("test1");
     Node test_2 = new Node("test2");
     Node test_3 = new Node("test3");
     Node test_4 = new Node("test4");
     Node test_5 = new Node("test5");
     Node test_6 = new Node("test6");

     root.addNode(test_2);
     root.addNode(test_3);
     root.addNode(test_4);
     root.addNode(test_5);
     root.addNode(test_6);

     displayTree(root);
     replaceNode(root, "test4", "hey");
     System.out.println("-------");
     displayTree(root);
  }
}

在测试 findNode 方法并看到它返回正确的对象后，我意识到无限循环是由我的 replaceNode 方法引起的。我只是不太确定它是如何引起的。

我通过删除 while 循环让它在一个案例中工作，但显然这对重复项不起作用，所以我想知道如何删除带有 oldDesc 的节点并替换它当可能有多个对象具有匹配的 oldDesc 数据时，使用包含 newDesc 的新对象。

Answer 1

您永远不会在 while 循环中更改 root 或 oldDesc

 while(replacedAllNodes == false) {
     Node replace = findNode(root, oldDesc);
     if(replace == null) { // No more nodes to replace
       replacedAllNodes = true;
       return;
  }
 replace = new Node(newDesc);
 root.addNode(replace);
}

如果你看

public static Node findNode(Node current, String desc) {
   Node result = null;
   if(current == null) {
     return null;
   }
   if(current.getDesc().equals(desc)) {
     return current;
   }
   if(current.getLeftNode() != null) {
     result = findNode(current.getLeftNode(), desc);
   }
   if(result == null) {
     result = findNode(current.getRightNode(), desc);
   }
   return result;
 }

如果 if(current.getDesc().equals(desc)) 条件匹配，replace 将永远是 root 所以你是卡在你的 while 循环中

更新:

• 如果您不必替换整个节点，您可以只在 while 循环结束时更新节点的描述。

代替

 replace = new Node(newDesc);
 root.addNode(replace);

做类似的事情:

  root.setDesc(newDesc);

(当然你必须先创建一个setDesc()方法)

• 如果你必须替换整个对象，你必须这样做:

代替

replace = new Node(newDesc);
root.addNode(replace);

做这样的事情:

replace = new Node(newDesc);
replace.setLeftNode(root.getLeftNode);
replace.setRightNode(root.getRightNode);

另外，您必须链接指向 root 的节点，以便它指向 replace ，就像以下示例之一(当然取决于您的根位于哪一侧) :

 nodeThatPointedToRoot.setLeftNode(replace);
 nodeThatPointedToRoot.setRightNode(replace);