二叉树和有序遍历
二叉树和有序遍历
提问于 2013-03-31 23:53:05
我正在尝试用Java快速实现一个二进制搜索树。哪个类最适合用来实现按顺序遍历的方法？(我听说过TreeMap类。但是看起来这个类不包含任何按顺序遍历的方法)。
回答 3
Stack Overflow用户
回答已采纳
发布于 2013-03-31 23:55:56
使用LinkedHashMap以插入顺序遍历，或使用TreeMap以比较顺序遍历http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html
Stack Overflow用户
发布于 2013-04-01 00:36:19
您可以随时创建自己的类，并使用所述类实现算法。
public class Node {
Node leftChild;
Node rightChild;
int parent;
Node(int parent) {
this.parent = parent;
}
}然后实现Binary Search Tree类。这是非常快的，但它是为了给你一个想法。
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);
}
}
}Stack Overflow用户
发布于 2013-06-12 13:53:50
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15731270
复制相关文章
相似问题
腾讯云开发者
