Java：如何实现一个通用的二叉搜索树？

Question

Java：如何实现一个通用的二叉搜索树？

10

到目前为止，我一直在编写一个名为Node的类

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;
        }
    }

二叉搜索树

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

现在我想要支持BinarySearchTree插入任何类型的节点，例如字符串、人员对象等。

我该如何将它变成通用型，以容纳任何类型的节点？

- daydreamer

1

你尝试过什么？你调查过Java泛型并了解 <T> 语法吗？ - Colin D

10个回答

4

只需将每个 Node 和 BinarySearchTree 类变成通用类：

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;
    }
}

和：

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

请注意Comparable扩展约束，您稍后需要使用它来强制实现树中节点的顺序。感谢zaske的建议。

- Tudor

嘿，这里为什么会有那么多的踩呢？ - Tudor

2

你必须强制 T 扩展 Comparable，或在 CTOR 中提供 Comparable<T>，否则您将无法执行搜索。 - Yair Zaslavsky

3

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);
        }
    }

}

- Victor

1

请注意，您的代码无法编译。
您在这里面临一些挑战 -
A. 将Node定义为通用类型 -

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

B. 您的搜索类也应该是通用的，并且签名应该是
。

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

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

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

这是必要的，以强制您仅提供实现Comparable接口的类型，以便您可以在树中执行搜索。

- Yair Zaslavsky

@trumpetlicks - 不需要在Node类中编写Comparable方法的代码。当使用BinaryTreeSearch时，当然不能创建未实现Comparable接口的类的节点。 - Yair Zaslavsky

0

我发现了一个SnapTreeMap，它实现了一个并发的AVL树系统，链接在这里。

- adv

0

你有两个选择:

1) 你可以使用泛型/模板。

2) 将你的树接收一个类型为 Object 而不是 int 的参数，让用户自行负责转换。

- namenamename

0

最近写了这篇文章。希望你会觉得它有用。

public class TreeMap<V extends Comparable<V>> {

private class Node {
    Node left, right;
    V value;
    public Node(V value) {
        this.value = value;
    }
}

private Node root;
private int size;

public int getSize() {
    return size;
}

public TreeMap() {
    this.root = null;
    this.size = 0;
}

public boolean isEmpty() {
    if (root == null) return true;
    else return false;
}

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

public boolean contains(V value) {
    return contains(root, value);
}

public void print() {
    print(root);
}

private boolean contains(Node node, V value) {
    if (value.compareTo(node.value) == 0) {
        return true;
    } else if (value.compareTo(node.value) < 0) {
        if (node.left == null) return false;
        else return contains(node.left, value);
    } else {
        if (node.right == null) return false;
        else return contains(node.right, value);
    }
}

private void print(Node node) {
    if (root == null) return;
    System.out.println(node.value);
    if (node.left != null) print(node.left);
    if (node.right != null) print(node.right);
}

private void insert(Node node, V value) {
    if(value.compareTo(node.value) <= 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);
    }
}

}

- LaurentBaj

0

最近写了这个。希望你觉得有用。

public class GenericBST<V extends Comparable<V>> {

private class Node {
    Node left, right;
    V value;
    public Node(V value) {
        this.value = value;
    }
}

private Node root;
private int size;

public int getSize() {
    return size;
}

public GenericBST() {
    this.root = null;
    this.size = 0;
}

public boolean isEmpty() {
    if (root == null) return true;
    else return false;
}

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

public boolean contains(V value) {
    return contains(root, value);
}

public void print() {
    print(root);
}

private boolean contains(Node node, V value) {
    if (value.compareTo(node.value) == 0) {
        return true;
    } else if (value.compareTo(node.value) < 0) {
        if (node.left == null) return false;
        else return contains(node.left, value);
    } else {
        if (node.right == null) return false;
        else return contains(node.right, value);
    }
}

private void print(Node node) {
    if (root == null) return;
    System.out.println(node.value);
    if (node.left != null) print(node.left);
    if (node.right != null) print(node.right);
}

private void insert(Node node, V value) {
    if(value.compareTo(node.value) <= 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);
    }
}

}

- LaurentBaj

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);


}

- Sanil

1

考虑到这是一个来自2012年的问题，您应该强调您的代码带来了什么，而其他答案没有提供。没有解释的“代码转储”并不是非常有用的。 - Nic3500

-1

关于第二个问题，你应该使用模板：

http://www.oracle.com/technetwork/articles/javase/generics-136597.html

关于第一个问题： http://en.wikipedia.org/wiki/Binary_search_algorithm http://en.wikipedia.org/wiki/Tree_rotation (insert)

也许这样阅读更快：

http://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml

好好学习！

- pedr0

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Petar Minchev · Accepted Answer

使用泛型：

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