所谓分治算法：就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解
下面展示一个有序数组转二分查找树的实现
首先是景点的二叉树结构
1 /**
2 * 二叉树的典型结构实现
3 *
4 * @author kangye
5 * @param <T>
6 */
7 public class BinaryNode<T>
{
8
9 private final T data;
10 private BinaryNode<T>
left;
11 private BinaryNode<T>
right;
12
13 public BinaryNode(T data) {
14 this.data =
data;
15 }
16
17 public T getData() {
18 return data;
19 }
20
21 public BinaryNode<T>
getLeft() {
22 return left;
23 }
24
25 public void setLeft(BinaryNode<T>
left) {
26 this.left =
left;
27 }
28
29 public BinaryNode<T>
getRight() {
30 return right;
31 }
32
33 public void setRight(BinaryNode<T>
right) {
34 this.right =
right;
35 }
36
37 public boolean hasLeft() {
38 return left !=
null;
39 }
40
41 public boolean hasRight() {
42 return right !=
null;
43 }
44
45 @Override
46 public boolean equals(Object o) {
47 if (
this ==
o)
48 return true;
49 if (!(o
instanceof BinaryNode))
50 return false;
51
52 BinaryNode that =
(BinaryNode) o;
53
54 if (!
data.equals(that.data))
55 return false;
56 if (left !=
null ? !left.equals(that.left) : that.left !=
null)
57 return false;
58 if (right !=
null ? !right.equals(that.right) : that.right !=
null)
59 return false;
60
61 return true;
62 }
63
64 @Override
65 public int hashCode() {
66 int result =
data.hashCode();
67 result = 31 * result + (left !=
null ? left.hashCode() : 0
);
68 result = 31 * result + (right !=
null ? right.hashCode() : 0
);
69 return result;
70 }
71
72 @Override
73 public String toString() {
74 return "BinaryNode{" + "data=" + data + '}'
;
75 }
76 }
基本算法
1 /**
2 * 将有序数组转换成一颗二叉查找树
3 *
4 * @author kangye
5 */
6 public class SortedArrayToBST {
7
8 /**
9 * 验证
10 *
11 * @author kangye
12 * @param sortedArray
13 * @return
14 */
15 public BinaryNode<Integer>
transform(Integer[] sortedArray) {
16 if (sortedArray ==
null || sortedArray.length == 0
) {
17 throw new IllegalArgumentException("You can't use a null or empty array."
);
18 }
19 return transformToBST(sortedArray, 0, sortedArray.length - 1
);
20 }
21
22 /**
23 * 分治算法 把一个复杂的问题分成:两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解
24 *
25 * @author kangye
26 * @param sortedArray 有序数组， 在分支中仍然保留完整数组
27 * @param bottom 起始位置
28 * @param top 结束为止
29 * @return
30 */
31 private static BinaryNode<Integer> transformToBST(Integer[] sortedArray,
int bottom,
int top) {
32 int center = (top + bottom) / 2
;
33 if (sortedArray.length == 1
) {
34 return new BinaryNode<Integer>(sortedArray[0
]);
35 }
else if (bottom >
top) {
36 return null;
37 }
else {
38 BinaryNode node =
new BinaryNode<Integer>
(sortedArray[center]);
39 node.setLeft(transformToBST(sortedArray, bottom, center - 1
));
40 node.setRight(transformToBST(sortedArray, center + 1
, top));
41 return node;
42 }
43 }
44
45 }
照例最后是单元测试
1 /**
2 * @author kangye.
3 */
4 public class SortedArrayToBSTTest {
5
6 private SortedArrayToBST sortedArrayToBST;
7
8 @Before
9 public void setUp() {
10 sortedArrayToBST =
new SortedArrayToBST();
11 }
12
13 @Test(expected = IllegalArgumentException.
class)
14 public void shouldNotAcceptNullArrays() {
15 sortedArrayToBST.transform(
null);
16 }
17
18 @Test(expected = IllegalArgumentException.
class)
19 public void shouldNotAcceptAnEmptyArray() {
20 Integer[] emptyArray =
new Integer[0
];
21 sortedArrayToBST.transform(emptyArray);
22 }
23
24 @Test
25 public void shouldReturnJustOneNodeIfTheArrayContainsJustOneElement() {
26 Integer[] array = { 1
};
27
28 BinaryNode<Integer> result =
sortedArrayToBST.transform(array);
29
30 assertEquals(
new Integer(1
), result.getData());
31 }
32 }
一个有意思的问题，转换成Python是个什么样子？
转载于:https://www.cnblogs.com/kangye1014/p/5044468.html
