1.树 Tree
定义
树是层次化的而非线性的。
树是由显示结点间关系的边（edge）相联而成的结点（node）集合。
如果树的每个结点都可以有任意数目子结点，则称为一般树。
如果树中每个结点的子结点数目不超过n，则称为n叉树。
如果树中每个结点只有两个子结点，则称为二叉树。
从根开始，沿着连接结点的边从一个结点到另一结点，构成一条路径（path），顺着路径可以到达树中任何一个结点。根和其他任何一个结点之间的路径是唯一的。
二叉树
如果二叉树中的每个叶子结点都恰好有两个子结点，则称为满二叉树。
如果二叉树中除最后一层外其余层都是满的，并且最后一层的叶子是从左向右填满，则称为完全二叉树。
如果n是一个满二叉树中的结点数，h是树的高度，则 
含有n个结点的完全二叉树或满二叉树的高度是log2(n+1)向上取整
树的Java接口
|
1
2
3
4
5
6
7
8
|
public
interface
TreeInterface<T> {
public
T getRootData();
public
int
getHieght();
public
int
getNumberOfNodes();
public
boolean
isEmpty();
public
void
clear();
}
|
树的遍历方法接口
|
1
2
3
4
5
6
7
|
public
interface
TreeIteratorInterface<T> {
public
Iterator<T> getPerorderIterator();
public
Iterator<T> getPostorderIterator();
public
Iterator<T> getInorderIterator();
public
Iterator<T> getLevelOrderIterator();
}
|
二叉树的接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public
interface
BinaryTreeInterface<T>
extends
TreeInterface<T>,
TreeIteratorInterface<T> {
/**
* 将已有的二叉树置为一棵新的单结点的二叉树
* @param rootData
*/
public
void
setTree(T rootData);
/**
* 将已有的二叉树置为一颗新的二叉树
* @param rootData 新树的根的数据对象
* @param leftTree 新树的左子树
* @param rightTree 新树的右子树
*/
public
void
setTree(T rootData, BinaryTreeInterface<T> leftTree,
BinaryTreeInterface<T> rightTree);
}
|
二叉树的实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public
class
BuildBinaryTree {
// 构建只含一个结点的树
BinaryTreeInterface<String> dTree =
new
BinaryTree<String>();
dTree.setTree(
"D"
);
BinaryTreeInterface<String> fTree =
new
BinaryTree<String>();
fTree.setTree(
"F"
);
BinaryTreeInterface<String> gTree =
new
BinaryTree<String>();
gTree.setTree(
"G"
);
BinaryTreeInterface<String> hTree =
new
BinaryTree<String>();
hTree.setTree(
"H"
);
// 构建更大的子树
BinaryTreeInterface<String> eTree =
new
BinaryTree<String>();
eTree.setTree(
"E"
, fTree, gTree);
BinaryTreeInterface<String> bTree =
new
BinaryTree<String>();
bTree.setTree(
"B"
, dTree, eTree);
BinaryTreeInterface<String> cTree =
new
BinaryTree<String>();
cTree.setTree(
"C"
, emptyTree, hTree);
BinaryTreeInterface<String> aTree =
new
BinaryTree<String>();
aTree.setTree(
"A"
, bTree, cTree);
}
|
堆
堆（heap）是其结点含有Comparable的对象并且每个结点含有的对象不小于（或不大于）其后代中的对象的完全二叉树。在最大堆中，结点中的对象大于等于其后代对象。在最小堆中，结点的对象小于等于其后代对象。
最大堆的接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public
interface
MaxHeapInterface<T
extends
Comparable<?
super
T>> {
// 将一个新元素插入堆
public
void
add(T newEntry);
// 删除并返回堆中最大元素，如果堆为空则返回null
public
T removeMax();
// 返回堆中最大的元素，如果堆为空则返回null
public
T getMax();
// 检查堆是否为空
public
boolean
isEmpty();
// 获得堆的大小
public
int
getSize();
// 删除堆中所有元素
public
void
clear();
}
|
优先队列
|
1
2
3
4
5
6
7
8
9
10
|
public
class
PriorityQueue<T
extends
Comparable<?
super
T>>
implements
PriorityQueueInterface<T>, Serializable {
private
MaxHeapInterface<T> pq;
public
PriorityQueue() {
pq =
new
MaxHeap<T>();
}
@Override
public
void
add(T newEntry) {
pq.add(newEntry);
}
}
|
2.二叉树的结点
二叉树结点的接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
public
interface
BinaryNodeInterface<T> {
/**
* 检索结点的数据部分
* @return 结点的数据部分中的对象 */
public
T getData();
/**
* 设置结点的数据部分
* @param newDdata 是一个对象 */
public
void
setData(T newData);
/**
* 检索结点的左（或右）子结点
* @return 结点的左（或右）子结点 */
public
BinaryNodeInterface<T> getLeftChild();
public
BinaryNodeInterface<T> getRightChild();
/**
* 将结点的的左子结点设为指定结点
* @param leftChild 将成为左子结点 */
public
void
setLeftChild(BinaryNodeInterface<T> leftChild);
/**
* 将结点的右子结点设为指定结点
* @param rightChild 将成为右子结点 */
public
void
setRightChild(BinaryNodeInterface<T> rightChild);
/**
* 检查结点是否有左（或右）子结点
* @return 如果有左（或右）子结点则返回true */
public
boolean
hasLeftChild();
public
boolean
hasRightChild();
/**
* 检查结点是不是叶子
* @return 如果是叶子则返回true */
public
boolean
isLeaf();
/**
* 计算以该结点为根的子树的结点数据
* @return 返回以该结点为根的子树的结点数目 */
public
int
getNumberOfNodes();
/**
* 计算以该结点为根的子树的高度
* @return 返回以该结点为根的子树的高度 */
public
int
getHeight();
/**
* 复制以该结点为根的子树
* @return 返回以该结点为根的子树的根 */
public
BinaryNodeInterface<T> copy();
}
|
BinaryNode的实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
public
class
BinaryNode<T>
implements
BinaryNodeInterface<T>, Serializable {
private
T data;
private
BinaryNode<T> left;
private
BinaryNode<T> right;
public
BinaryNode() {
this
(
null
);
}
public
BinaryNode(T dataPortion) {
this
(dataPortion,
null
,
null
);
}
public
BinaryNode(T dataPortion, BinaryNode<T> leftChild,
BinaryNode<T> rightChild) {
data = dataPortion;
left = leftChild;
right = rightChild;
}
public
T getData() {
return
data;
}
public
void
setData(T newData) {
data = newData;
}
public
BinaryNodeInterface<T> getLeftChild() {
return
left;
}
public
BinaryNodeInterface<T> getRightChild() {
return
right;
}
public
void
setLeftChild(BinaryNodeInterface<T> leftChild) {
left = (BinaryNode<T>) leftChild;
}
public
void
setRightChild(BinaryNodeInterface<T> rightChild) {
right = (BinaryNode<T>) rightChild;
}
public
boolean
hasLeftChild() {
return
left !=
null
;
}
public
boolean
hasRightChild() {
return
right !=
null
;
}
public
boolean
isLeaf() {
return
(left ==
null
) && (right ==
null
);
}
}
|
本文转自 LinkedKeeper 51CTO博客，原文链接：http://blog.51cto.com/sauron/1227342，如需转载请自行联系原作者
