Бинарное дерево на основе строк и вставка - PullRequest
Новая
       5

Бинарное дерево на основе строк и вставка

0 голосов
/ 16 ноября 2018

Двоичное дерево скорее не использует сравнение, пользователь вводит строку name узла, к которому он хочет добавить левого или правого дочернего элемента, если у узла уже есть дочерний элемент для любого из двух, и он не будет перезаписывать это.

У меня есть некоторые трудности, это не мешает перезаписать ранее существовавший узел и не всегда запоминает его собственного потомка.

Пожалуйста, скажите мне, что я упустил что-то простое или мне нужно все переделать, и если да, то как мне сделать это на этот раз.

Спасибо за помощь в продвинутом. 

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 Это сработало Такой родитель не существует Такой родитель не существует 1 Сработало

«Сработало» - это отметка, если программа завершает левые вставки «1» показывает значение узла родительского элемента, к которому добавляется новая вставка

1 Ответ

0 голосов
/ 16 ноября 2018

Я обновил логику, чтобы найти родительский узел. Он вернет ноль, если он не существует, иначе он вернет родительский узел. 

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
...