Java : Wie implementiere ich einen generischen Binären Suchbaum?

Bis jetzt, habe ich schriftlich eine Knoten-Klasse, die als

class Node {
        private  value;
        private Node left;
        private Node right;

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

- und Binary-Search-Tree als

public class BinarySearchTree {
    private Node root;

    public BinarySearchTree(int value) {
        root = new Node(value);
    }

    public void insert(int value) {
      Node node = new Node(value);
        //insert logic goes here to search and insert
    }
}

Nun möchte ich unterstützen BinarySearchTree um Knoten einfügen jeglicher Art wie strings, Menschen

Wie kann ich es allgemein zu halten, jede Art?

Was haben Sie versucht? Haben Sie recherchiert, java generics und wissen Sie über die <T> syntax?

InformationsquelleAutor daydreamer | 2012-06-29

  1. 15

    Generika verwendet werden:

    class Node<T extends Comparable<T>> {
        private T value;
        ...
}

public class BinarySearchTree<T extends Comparable<T>> {
    private Node<T> root;

    public BinarySearchTree(T value) {
        root = new Node<T>(value);
    }

    public void insert(T value) {
      Node<T> node = new Node<T>(value);
        //insert logic goes here to search and insert
    }
}
    Downvoter - bitte erklären:)
    Es gibt eine serielle downvoter hier in der Nähe.
    danke für die Informationen:)
    Keine Ahnung, wer die nach-unten-Wähler, aber achten Sie darauf, dass Sie sich durchsetzen muss T zu erweitern vergleichbar, da es sonst unmöglich sein wird, zu implementieren, die den Vergleich code.
    Es muss auch Comparable<T> völlig korrekt. 🙂

    InformationsquelleAutor Petar Minchev

  2. 2

    Nur machen alle Node und BinarySearchTree generische Klassen:

    class Node<T extends Comparable<T>> {
    private T value;
    private Node<T> left;
    private Node<T> right;

    public Node(T value) {
        this.value = value;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }
}

    und: 

    class BinarySearchTree<T extends Comparable<T>> {
    private Node<T> root;

    public BinarySearchTree(T value) {
        root = new Node<T>(value);
    }

    public void insert(T value) {
      Node<T> node = new Node<T>(value);
        //insert logic goes here to search and insert
    }
}

    Hinweis: die Comparable Erweiterung Einschränkung, die Sie später brauchen wird, um zu erzwingen Bestellung Knoten im Baum. Dank zaske für die Anregung.

    Hey, was ist mit allen downvoting hier?
    Sie muss durchsetzen, T zu erweitern vergleichbar, oder Comprable<T> am TOR, sonst werden Sie nicht in der Lage sein, um die Suche durchzuführen.
    Guter Vorschlag.

    InformationsquelleAutor Tudor

  3. 1

    Bitte nicht deinen code nicht kompilieren.

    Sie haben ein paar Herausforderungen -

    A. Definieren von Knoten als Generic - 

    public class Node<T> {
   private T value;
   //... here goes the rest of your code
}

    B. Ihre Suche Klasse auch sollte generisch sein und die Signatur sollte es sein, 

    public class BinarySearchTree <T extends Comparable<T>> {

   public BinarySearchTree(T value) {
      //Do your logic here
   }

   public void insert(T value)  {
        //Do your logic here
   }
}

    Dies ist erforderlich, um zu erzwingen, Sie bieten nur Typen, die Umsetzung Vergleichbar sind, so werden Sie in der Lage zu führen Sie die Suche in dem Baum.

    Guter Punkt, es muss Vergleichbar sein.
    Ich denke, der Knoten zu erweitern, vergleichbar auch!!!!!
    Nein. Es ist kein code innerhalb der Klasse Knoten muss Methoden Vergleichbar. Natürlich, Bei der Verwendung von BinaryTreeSearch, es gibt keine Möglichkeit zum erstellen von Knoten für Klassen, die nicht umsetzen, Compparable.

    InformationsquelleAutor Yair Zaslavsky

  4. 0

    Haben Sie zwei Möglichkeiten:

    1) Man kann in generics/templates.

    2) Haben Ihren Baum zu nehmen, in eine Art Object statt int und haben die Benutzer sind verantwortlich für das Gießen.

    option 2 ist eine schlechte Wahl.

    InformationsquelleAutor Conor Sherman

  5. 0

    Fand ich eine SnapTreeMap, die eine gleichzeitige AVL-Baum system hier.

    InformationsquelleAutor adv

  6. 0
    Please find the BST using Generics, U can find more information on below link

    https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/code/BST.java

    public class BinarySearchTree< T extends Comparable<T>> {
    Node root;
    class Node {
        T data;
        Node left;
        Node right;

        public Node(T data) {
            this.data = data;
        }
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void insert(T value) {
        if(isEmpty())
            root = new Node(value);
        else
            insert(root, value);
    }

    private void insert(Node node, T value) {

        if(value.compareTo(node.data) < 0) {
            if(node.left == null)
                node.left = new Node(value);
            else
                insert(node.left, value);
        }
        else {
            if(node.right == null)
                node.right = new Node(value);
            else
                insert(node.right, value);
        }
    }

}

    InformationsquelleAutor Victor

  7. 0
    public class TNode<T extends Comparable<T>> {
    T data;
    public TNode<T> left;
    public TNode<T> right;

    public TNode(T data){
        this.data = data;
    }
}


import java.util.ArrayList;
import java.util.List;

public class BinaryTree<T extends Comparable<T>> {
private TNode root;

public TNode getRoot() {
    return this.root;
}

public void add(T data) {
    TNode<T> newNode = new TNode<T>(data);
    if (root == null) {
        root = newNode;
    } else {
        TNode<T> tempNode = root;
        TNode<T> prev = null;
        while (tempNode != null) {
            prev = tempNode;
            if (data.compareTo(tempNode.data) > 0) {
                tempNode = tempNode.right;
            } else {
                tempNode = tempNode.left;
            }
        }
        if (data.compareTo(prev.data) < 0) {
            prev.left = newNode;
        } else {
            prev.right = newNode;
        }

    }
}


public void traverseInOrder(TNode<T> root, List<T> storageList) {
    if (root != null) {
        traverseInOrder(root.left, storageList);
        storageList.add(root.data);
        traverseInOrder(root.right, storageList);
    }
}

public void traversePreOrder(TNode<T> root, List<T> storageList) {
    if (root != null) {
        storageList.add(root.data);
        traversePreOrder(root.left, storageList);
        traversePreOrder(root.right, storageList);
    }
}

public void traversePostOrder(TNode<T> root, List<T> storageList) {
    if (root != null) {
        traversePostOrder(root.left, storageList);
        traversePostOrder(root.right, storageList);
        storageList.add(root.data);
    }
}

public void printList(List<T> list) {
    for (T item : list) {
        System.out.println(item);
    }
}


public static void main(String args[]) {
    BinaryTree<Integer> bTree = new BinaryTree<>();
    bTree.add(50);
    bTree.add(30);
    bTree.add(60);
    bTree.add(25);
    bTree.add(40);
    bTree.add(35);
    bTree.add(70);
    bTree.add(65);

    System.out.println("#### Inorder Traversal ####");
    List<Integer> inOrderList = new ArrayList<>();
    bTree.traverseInOrder(bTree.getRoot(), inOrderList);
    bTree.printList(inOrderList);

    System.out.println("#### Pre Traversal ####");
    List<Integer> preOrderList = new ArrayList<>();
    bTree.traversePreOrder(bTree.getRoot(), preOrderList);
    bTree.printList(preOrderList);


    System.out.println("#### Post Traversal ####");
    List<Integer> postOrderList = new ArrayList<>();
    bTree.traversePostOrder(bTree.getRoot(), postOrderList);
    bTree.printList(postOrderList);


}
    Man bedenkt, dass dies eine Frage von 2012 ist, sollten Sie hervorheben, was Sie bringen mit Ihrem code, dass die anderen Antworten nicht bereits bieten. Ein "code dump" ohne Erklärungen ist nicht super nützlich.

    InformationsquelleAutor Sanil

Schreibe einen Kommentar