基于字符串的二叉树和插入

Question

二叉树不使用比较而是，用户输入他们想要添加左或右child的节点的字符串name，如果节点已经有一个[=31] =] 对于两者中的任何一个，它都不会覆盖它。

我遇到了一些困难，它并不能阻止它覆盖 pre-existing 节点，而且它并不总是记得它自己的 child。

请告诉我我是不是遗漏了一些简单的东西，或者我是否需要重做所有的事情，如果是的话，这次我应该怎么做。

感谢您的提前帮助。

public class Node {

   private String name;
   private Node leftChild;
   private Node rightChild;
   private Node parent;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   public Node getLeftChild() {
       return leftChild;
   }

   public void setLeftChild(Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return rightChild;
   }

   public void setRightChild(Node rightChild) {
       this.rightChild = rightChild;
   }

   public Node getParent() {
       return parent;
   }

   public void setParent(Node parent) {
       this.parent = parent;
   }

   public void displayNode() // display ourselves{
      System.out.println(name);
   }

}

public class Tree {
   private Node root;

   public Tree() {
       root = null;
   }

   public void insertRoot(String rootName) {
       if (root == null) {
          Node newNode = new Node();
          newNode.setName(rootName);
          root = newNode;
       } else {
          System.out.println("There is already a root");
       }
   }

   public void insertLeftChild(String parentName, String childName) {
      Node temp = new Node();
      Node current = parent(parentName, root, temp);

     if (current.getName() == null) {
        System.out.println("No such parent exists");
     } else if (current.getLeftChild() == null) {

        Node newNode = new Node();
        newNode.setName(childName);

        current.displayNode();

        newNode.setParent(current);

        current.setLeftChild(newNode);
        System.out.println("It worked");
     } else if (current.getLeftChild() != null) {
        System.out.println("They already have a left child");
     }
  }

  public void insertRightChild(String parentName, String childName) {
     Node temp = new Node();

     Node current = parent(parentName, root, temp);

     if (current.getName() == null) {
        System.out.println("No such parent exists");
     } else if (current.getRightChild() == null) {
        Node newNode = new Node();
        newNode.setName(childName);

        newNode.setParent(current);
        current.setRightChild(newNode);
     } else if (current.getRightChild() != null) {
        System.out.println("They already have a right child");
     }
  }

  public Node parent(String parentName, Node current, Node found) {
     if (current != null) {
        if (current.getName().equals(parentName)) {
           found.setName(parentName);
           found.setParent(current.getParent());
           found.setLeftChild(current.getLeftChild());
           found.setRightChild(current.getRightChild());

           return found;
        }

        parent(parentName, current.getLeftChild(), found);
        parent(parentName, current.getRightChild(), found); // right child  
     }
     return found;
  }
}

这里是主要方法

public class Demo {

public static void main(String[] args) {

    Tree t = new Tree();

    t.insertRoot("1");

    t.insertLeftChild("1", "2");

    t.insertLeftChild("2", "3");

    t.insertLeftChild("3", "4");

    t.insertLeftChild("1", "3");

    t.insertRightChild("7", "8");   
 }
}

这是当前的结果

1 有效不存在这样的 parent 不存在这样的 parent 1个成功了

"It worked" 是程序是否完成左插入的标记 “1”显示 parent 的节点值，新插入内容正在添加到

Answer 1

我已经更新了查找父节点的逻辑。如果它不存在，它将 return null 否则它将 return 父节点。

public Node parent(String parentName, Node root) {
    if (root != null) {
        if (root.getName().equals(parentName)) {
            return root;
        } else {
            Node found = parent(parentName, root.getLeftChild());
            if (found == null) {
                found = parent(parentName, root.getRightChild());
            }
            return found;
        }
    } else {
        return null;
    }
}

完整代码..

class Node {

private String name;
private Node leftChild;
private Node rightChild;
private Node parent;

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public Node getLeftChild() {
    return leftChild;
}

public void setLeftChild(Node leftChild) {
    this.leftChild = leftChild;
}

public Node getRightChild() {
    return rightChild;
}

public void setRightChild(Node rightChild) {
    this.rightChild = rightChild;
}

public Node getParent() {
    return parent;
}

public void setParent(Node parent) {
    this.parent = parent;
}

public void displayNode() {

    System.out.println(name);
}

}



public class Tree {

private Node root;

public Tree() {
    root = null;
}

public void insertRoot(String rootName) {
    if (root == null) {
        Node newNode = new Node();
        newNode.setName(rootName);
        root = newNode;
    } else {
        System.out.println("There is already a root");
    }
}

public void insertLeftChild(String parentName, String childName) {
    Node parent = parent(parentName, root);

    if (parent == null) {
        System.out.println("No such parent exists");
    } else if (parent.getLeftChild() == null) {

        Node newNode = new Node();
        newNode.setName(childName);

        parent.displayNode();

        newNode.setParent(parent);

        parent.setLeftChild(newNode);
        System.out.println("It worked");
    } else if (parent.getLeftChild() != null) {
        System.out.println("They already have a left child");
    }
}

public void insertRightChild(String parentName, String childName) {

    Node parent = parent(parentName, root);

    if (parent == null) {
        System.out.println("No such parent exists");
    } else if (parent.getRightChild() == null) {
        Node newNode = new Node();
        newNode.setName(childName);

        newNode.setParent(parent);
        parent.setRightChild(newNode);
    } else if (parent.getRightChild() != null) {
        System.out.println("They already have a right child");
    }
}

public Node parent(String parentName, Node root) {
    if (root != null) {
        if (root.getName().equals(parentName)) {
            return root;
        } else {
            Node found = parent(parentName, root.getLeftChild());
            if (found == null) {
                found = parent(parentName, root.getRightChild());
            }
            return found;
        }
    } else {
        return null;
    }
}

public static void main(String[] args) {

    Tree t = new Tree();

    t.insertRoot("1");

    t.insertLeftChild("1", "2");

    t.insertLeftChild("2", "3");

    t.insertLeftChild("3", "4");

    t.insertLeftChild("1", "3");

    t.insertRightChild("7", "8");
}
}

输出..

1
It worked
2
It worked
3
It worked
They already have a left child
No such parent exists

基于字符串的二叉树和插入

String based Binary tree and insertion

java

binary-tree

data-structures