二叉树 Binary Tree
2019-06-27 20:52:02
/** * @ClassName BinaryTree * @Author wangyudi * @Date 2019/6/27 17:51 * @Version 1.0 * @Description 二叉数数据结构 * 成员变量：根结点 root 结点类 Node * 成员方法：大小 size、获取值 get、加入值 put、 * 最大键 max、最小键 min、向下取整floor、向上取整ceiling、 * 根据排名选择 select、排名 rank、 * 删除最小键 deleteMin、删除任意键 delete; */ public class BinaryTree<Key extends Comparable<Key>, Value> { public Node root;//根结点，二叉树只要一个根结点即可找到所有的结点 //匿名内部类，用于表示二叉树的抽象数据结构--结点 //结点一共含有5个成员变量 private class Node { Key key; //必须是Comparable对象 Value value; int count;//用于rank() Node left; Node right; public Node(Key key, Value value, int count, Node left, Node right) { this.key = key; this.value = value; this.count = count; this.left = left; this.right = right; } } public int size() { return size(root); } public int size(Node node) { if (node == null) return 0; //不可缺少 else return node.count; } public Value get(Key key) { return get(key, root); } public Value get(Key key, Node node) { if (node == null) return null; //没有找到 int cmp = key.compareTo(node.key); //根据cmp的值确定是否为根结点或在左/右树寻找 if (cmp > 0) { return get(key, node.right); } else if (cmp < 0) { return get(key, node.left); } else { return node.value; //找到 } } public void put(Key key, Value value) { root = put(key, value, root); } public Node put(Key key, Value value, Node node) { if (node == null) { //没有找到相同的键，则新键一个结点，并将自身的引用返回给上一结点（父结点） return new Node(key, value, 1, null, null); } int cmp = key.compareTo(node.key);//根据cmp的值确定是否为根结点或在左/右树寻找 if (cmp > 0) { node.right = put(key, value, node.right); } else if (cmp < 0) { node.left = put(key, value, node.left); } else { //找到相同的key node.value = value; return node; } node.count = size(node.left) + size(node.right) + 1; //该表大小 return node; } public Node max(Node node) { if (node.right == null) return node; //直到某一结点的右结点为null，返回该结点 return max(node.right); } public Node min(Node node) { //直到某一结点的左结点为null，返回该结点 if (node.left == null) return node; return min(node.left); } //向下取整 //如果key比根节点小，则floor结点一定在左子树中（如果有）。 //如果key比根节点大，则floor在右子树中或是根结点。 //如果根节点为null，则没有找到 public Node floor(Key key, Node node) { if (node == null) return null; int cmp = key.compareTo(node.key); if (cmp < 0) { return floor(key, node.left); } else if (cmp > 0) { Node temp = floor(key, node.right); //可能在右子树中 if (temp != null) return temp; //存在，则floor结点为右子树中找到的结点 return node;//如果右子数中不存在，则floor(key,node.right)返回null，floor结点为根结点 } else { return node; } } //基本思路和floor相同 //如果比根结点大，则在右树 //如果比根结点小，则可能在左树或根结点 //如果根节点为null，则没有找到 public Node ceiling(Key key, Node node) { if (node == null) return null; int cmp = key.compareTo(node.key); if (cmp > 0) { return floor(key, node.right); } else if (cmp < 0) { Node temp = ceiling(key, node.left); //可能在左子树中 if (temp != null) return temp; return node; } else { return node; } } //查找排名为k的键的值 public Value select(int k) { return select(root, k).value; } public Node select(Node node, int k) { if (node == null) return null; //根结点为null,则表示没有找到 if (size(node.left) == k) return node; else if (size(node.left) > k) { return select(node.left, k); } else { return select(node.right, k - 1 - size(node.left)); //在右数中寻找时，要调整排名 } } //键值为key的结点在树中的排名 public int rank(Node node, Key key) { if (node == null) return 0; //根结点为null,则返回0，表示排名为0 int cmp = key.compareTo(node.key); if (cmp == 0) { return size(node.left); } else if (cmp > 0) { return size(node.left) + 1 + rank(node.right, key); //在右子树中查找时调整返回值 } else { return rank(node.left, key); } } public void deleteMin() { root = deleteMin(root); } //删除最小的结点 //思路：最小的结点是递归后，左子树为null的那个结点；删除的方法，是将该结点的右子树返回给上次递归调用的结点。 public Node deleteMin(Node node) { if (node.left != null) { node.left = deleteMin(node.left); node.count = size(node.left) + size(node.right) + 1; //调整大小 return node; //不是被删除的结点，返回自身结点给上次递归调用的结点。 } else { return node.right; } } public void delete(Key key) { root = delete(key, root); } //删除某一结点 //根据cmp的值,选择在左/右子树中删除结点 //如果递归中，根结点为null,则表示没有找到该键，返回空 //如果递归中找到，根结点便是需要删除的结点，有分为两种去情况 //情况一：要求删除的结点没有左/右子树，返回右/左子树根结点,被删除的结点会被GC清理。 //情况二：要求删除的结点右左和右子树， // 1.保存被删除的根结点temp 2.使用min()方法，在被删除结点的右自书中找到后记结点node 3.使用deleteMin()方法，在被删结点的右子树中删除后继结点 // 4.返回右子树根结点给后继结点的右结点 5.被删结点的左子树结点给后继结点 6.返回后继结点给上一次的递归 //调整大小，没有删除操作的结点，放回自身根结点 public Node delete(Key key, Node node) { if (node == null) return null;//没找到 int cmp = key.compareTo(node.key); if (cmp > 0) { node.right = delete(key, node.right); } else if (cmp < 0) { node.left = delete(key, node.left); } else { if (node.left == null) return node.right; if (node.right == null) return node.left; Node temp = node; //为了获得left子树结点 node = min(node.right); node.right = deleteMin(temp.right); node.left = temp.left; } node.count = size(node.right) + size(node.left) + 1; return node; } public void display() { display(root); } public void display(Node node) { if (node == null) return; display(node.left); System.out.print(node.value + " "); display(node.right); }
//返回支持迭代获取数据的数据结构
public Iterable<Value> values() {
return values(min().key, max().key);
}
public Iterable<Value> values(Key lo, Key hi) {
ArrayList<Value> valueArrayList = new ArrayList<>();
values(root, lo, hi, valueArrayList);
return valueArrayList;
}
public void values(Node node, Key lo, Key hi, ArrayList<Value> arr) {
if (node == null) return;
int cmplo = lo.compareTo(node.key);
int cmphi = hi.compareTo(node.key);
if (cmplo < 0) {
values(node.left, lo, hi, arr);
}
if (cmplo <= 0 && cmphi >= 0) {
arr.add(node.value);
}
if (cmphi > 0) {
values(node.right, lo, hi, arr);
}
} }
/** * @ClassName TestCase * @Author wangyudi * @Date 2019/6/27 20:11 * @Version 1.0 * @Description 测试用例 */ public class TestCase { public static void main(String[] args) { BinaryTree<Integer, String> tree = new BinaryTree<>(); tree.put(12,"12.."); tree.put(2,"2.."); tree.put(34,"34.."); tree.put(17,"17.."); tree.put(55,"55.."); tree.put(214,"214.."); tree.display(); System.out.println(); tree.deleteMin(); tree.delete(12); tree.delete(222); tree.delete(214); tree.display(); System.out.println(); System.out.println(tree.select(0)); System.out.println(tree.rank(tree.root,55)); } } //结果 2.. 12.. 17.. 34.. 55.. 214.. 17.. 34.. 55.. 17.. 2