java - 二叉搜索树和中序遍历

Question

我正在尝试在 Java 中快速实现二进制搜索树。具有按顺序遍历方法的最佳使用类是什么？（我听说过 TreeMap 类。但看起来该类不包含任何按顺序遍历的方法）。

Answer 1

使用 LinkedHashMap 以插入顺序遍历或 TreeMap 以比较顺序遍历 http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

Answer 2

您总是可以创建自己的类，并使用所述类实现算法。

public class Node {
    Node leftChild;
    Node rightChild;
    int parent;

    Node(int parent) {
        this.parent = parent;
    }
}

然后实现二叉搜索树类。这是非常快的，但它是为了给你一个想法。

public class BSTree {
Node root;

BSTree() {
    root = null;
}

public void insert(Node node, int value) {
    if (value >= node.parent) {
        if (!(node.rightChild == null)) {
            insert(node.rightChild, value);
        } else {
            node.rightChild = new Node(value);
        }
    } else if (value < node.parent) {
        if (!(node.leftChild == null)) {
            insert(node.leftChild, value);
        } else {
            node.leftChild = new Node(value);
        }
    } else {
        root = new Node(value);
    }
}


public boolean delete(Node node, int value) {
    if (root == null) {
        return false;
    } else if (value > root.parent) {
        return delete(root.rightChild, value);
    } else if (value < root.parent) {
        return delete(root.leftChild, value);
    } else {
        if (root.leftChild == null && root.rightChild == null) {
            root = null;
            return true;
        } else if (root.leftChild == null && root.rightChild != null) {
            root = root.rightChild;
            return true;
        } else if (root.leftChild != null && root.rightChild == null) {
            root = root.leftChild;
            return true;
        } else {
                            Node minRight = minNode(root.rightChild);
                            root = minRight;
                            delete(minRight, minRight.parent);
                            return true;
        }
    }
}

public Node minNode(Node node) {
    if (node.leftChild == null) {
        return node;
    } else {
        return minNode(node.leftChild);
    }
}
}

Answer 3

TreeSet 类可能是您想要的

class Node implements Comparable<Node>;   // implements your Node class
TreeSet<Node> set = new TreeSet<Node>();

// after adding a bunch of nodes into set
Iterator<Node> it = set.iterator();
while(it.hasNext()){
    Node current = it.next();
    System.out.println(current); // operate on current node
}

Node first = set.first();    // smallest element in set
Node second = set.ceiling(first);    // the successor method