Merge pull request onlyliuxin#24 from akinaru-lu/master

Greastate · web-flow · commit 4f52a986faa6 · 2017-02-26T10:54:31.000+08:00
2-26 assignment
diff --git a/group08/729770920/2-26/src/com/coding/basic/ArrayList.java b/group08/729770920/2-26/src/com/coding/basic/ArrayList.java
@@ -24,7 +24,7 @@ public void add(int index, E e){
             throw new IndexOutOfBoundsException(Integer.toString(index));
         }
 		if (data.length == size) {
-            ensureCapacity(size * 2 + 1);
+            ensureCapacity(size + size >> 1 + 1);
         }
         for (int i = size++; i > index; --i) {
             data[i] = data[i - 1];
diff --git a/group08/729770920/2-26/src/com/coding/basic/BinaryTree.java b/group08/729770920/2-26/src/com/coding/basic/BinaryTree.java
@@ -0,0 +1,105 @@
+package com.coding.basic;
+
+public class BinaryTree<E extends Comparable<? super E>> {
+    BinaryTreeNode root = null;
+
+    public BinaryTree() {
+    }
+
+    public boolean isEmpty() {
+        return root == null;
+    }
+
+    public void insert(E e) {
+        root = insert(root, e);
+    }
+
+    private BinaryTreeNode<E> insert(BinaryTreeNode<E> node, E e) {
+        if (node == null) {
+            node = new BinaryTreeNode(e, null, null);
+        }
+        int compareResult = ((Comparable) e).compareTo(node.data);
+        if (compareResult < 0) {
+            node.left = insert(node.left, e);
+        } else if (compareResult > 0) {
+            node.right = insert(node.right, e);
+        }
+        return node;
+    }
+
+    public void clear() {
+        root = null;
+    }
+
+    public boolean contains(E e) {
+        return contains(root, e);
+    }
+
+    private boolean contains(BinaryTreeNode<E> node, E e) {
+        if (node == null) {
+            return false;
+        }
+        int compareResult = ((Comparable) e).compareTo(node.data);
+        if (compareResult < 0) {
+            return contains(node.left, e);
+        } else if (compareResult > 0) {
+            return contains(node.right, e);
+        }
+        // matching
+        return true;
+    }
+
+    private BinaryTreeNode<E> findMin(BinaryTreeNode<E> node) {
+        if (node != null) {
+            while (node.left != null) {
+                node = node.right;
+            }
+        }
+        return node;
+    }
+
+    private BinaryTreeNode<E> findMax(BinaryTreeNode<E> node) {
+        if (node != null) {
+            while (node.right != null) {
+                node = node.right;
+            }
+        }
+        return node;
+    }
+
+    public void remove(E e) {
+        root = remove(root, e);
+    }
+
+    private BinaryTreeNode<E> remove(BinaryTreeNode<E> node, E e) {
+        if (node == null) {
+            return node;
+        }
+        int compareResult = ((Comparable) e).compareTo(node.data);
+        if (compareResult < 0) {
+            node.left = remove(node.left, e);
+        } else if (compareResult > 0) {
+            node.right = remove(node.right, e);
+        }
+        // matching
+        if (node.left != null && node.right != null) { // two children
+            node.data = (E) findMax(node.right).data;
+            node.right = remove(node.right, node.data);
+        } else { // one child
+            node = (node.left != null) ? node.left : node.right;
+        }
+        return node;
+    }
+
+    private class BinaryTreeNode<E> {
+        E data;
+        BinaryTreeNode left;
+        BinaryTreeNode right;
+
+        public BinaryTreeNode(E e, BinaryTreeNode<E> l, BinaryTreeNode<E> r) {
+            data = e;
+            left = l;
+            right = r;
+        }
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -24,7 +24,7 @@ public void add(int index, E e){`
`24`	`24`	`throw new IndexOutOfBoundsException(Integer.toString(index));`
`25`	`25`	`}`
`26`	`26`	`if (data.length == size) {`
`27`		`- ensureCapacity(size * 2 + 1);`
	`27`	`+ ensureCapacity(size + size >> 1 + 1);`
`28`	`28`	`}`
`29`	`29`	`for (int i = size++; i > index; --i) {`
`30`	`30`	`data[i] = data[i - 1];`