完成二叉树

miniyk2012 · miniyk2012 · commit 250c46efb360 · 2017-02-25T10:02:24.000+08:00
diff --git a/group02/812350401/.gitignore b/group02/812350401/.gitignore
@@ -1,2 +1,3 @@
 /bin/
 /lib/
+/src/java_training
diff --git a/group02/812350401/src/com/github/miniyk2012/coding2017/basic/BinaryTreeNode.java b/group02/812350401/src/com/github/miniyk2012/coding2017/basic/BinaryTreeNode.java
@@ -1,32 +1,55 @@
 package com.github.miniyk2012.coding2017.basic;
 
-public class BinaryTreeNode {
+public class BinaryTreeNode <E extends Comparable<E>> {
+	private E data;
+	private BinaryTreeNode<E> left;
+	private BinaryTreeNode<E> right;
 	
-	private Object data;
-	private BinaryTreeNode left;
-	private BinaryTreeNode right;
-	
-	public Object getData() {
+	public BinaryTreeNode(E x) {
+		data = x;
+	}
+	public E getData() {
 		return data;
 	}
-	public void setData(Object data) {
+	public void setData(E data) {
 		this.data = data;
 	}
-	public BinaryTreeNode getLeft() {
+	public BinaryTreeNode<E> getLeft() {
 		return left;
 	}
-	public void setLeft(BinaryTreeNode left) {
+	public void setLeft(BinaryTreeNode<E> left) {
 		this.left = left;
 	}
-	public BinaryTreeNode getRight() {
+	public BinaryTreeNode<E> getRight() {
 		return right;
 	}
-	public void setRight(BinaryTreeNode right) {
+	public void setRight(BinaryTreeNode<E> right) {
 		this.right = right;
 	}
 	
-	public BinaryTreeNode insert(Object o){
-		return  null;
+	public BinaryTreeNode<E> insert(E o){
+		BinaryTreeNode<E> node = new BinaryTreeNode<E>(o);
+		boolean left = true; 
+		BinaryTreeNode<E> currentNode = this;
+		BinaryTreeNode<E> previousNode = null;
+		
+		while (currentNode != null) {
+			previousNode = currentNode;
+			int compareTo = node.getData().compareTo(currentNode.getData());
+			if (compareTo <= 0) { // 小于，往左插入
+				currentNode = currentNode.left;
+				left = true;
+			} else {
+				currentNode = currentNode.right;
+				left = false;
+			}
+		}
+		if (left) {
+			previousNode.left = node;
+		} else {
+			previousNode.right = node;
+		}
+		return  node;
 	}
 	
 }
diff --git a/group02/812350401/src/com/github/miniyk2012/coding2017/basic/test/BinaryTreeNodeTest.java b/group02/812350401/src/com/github/miniyk2012/coding2017/basic/test/BinaryTreeNodeTest.java
@@ -8,26 +8,24 @@
 
 public class BinaryTreeNodeTest {
 
-	private BinaryTreeNode binaryTreeNode;
+	private BinaryTreeNode<Integer> binaryTreeNode;
 
 	@Before
 	public void setUpBinaryTreeNode() {
-		binaryTreeNode = new BinaryTreeNode();
+		binaryTreeNode = new BinaryTreeNode<Integer>(4);
 	}
 
 	@Test
 	public void testBinaryTreeNodeFunctional() {
-		binaryTreeNode.insert(4);
 		binaryTreeNode.insert(1);
 		binaryTreeNode.insert(3);
 		binaryTreeNode.insert(5);
 		binaryTreeNode.insert(2);
-		assertEquals(4, binaryTreeNode.getData());
-		assertEquals(1, binaryTreeNode.getLeft().getData());
-		assertEquals(5, binaryTreeNode.getRight().getData());
-		assertEquals(3, binaryTreeNode.getLeft().getRight().getData());
-		assertEquals(2, binaryTreeNode.getLeft().getRight().getLeft().getData());
-		// binaryTreeNode.print();
+		assertEquals(new Integer(4), binaryTreeNode.getData());
+		assertEquals(new Integer(1), binaryTreeNode.getLeft().getData());
+		assertEquals(new Integer(5), binaryTreeNode.getRight().getData());
+		assertEquals(new Integer(3), binaryTreeNode.getLeft().getRight().getData());
+		assertEquals(new Integer(2), binaryTreeNode.getLeft().getRight().getLeft().getData());
 	}
 
 }

Original file line number	Diff line number	Diff line change
`@@ -1,2 +1,3 @@`
`1`	`1`	`/bin/`
`2`	`2`	`/lib/`
	`3`	`+/src/java_training`