更新时间:2022-08-31 07:58:48
定义
树是层次化的而非线性的。
树是由显示结点间关系的边(edge)相联而成的结点(node)集合。
如果树的每个结点都可以有任意数目子结点,则称为一般树。
如果树中每个结点的子结点数目不超过n,则称为n叉树。
如果树中每个结点只有两个子结点,则称为二叉树。
从根开始,沿着连接结点的边从一个结点到另一结点,构成一条路径(path),顺着路径可以到达树中任何一个结点。根和其他任何一个结点之间的路径是唯一的。
二叉树
如果二叉树中的每个叶子结点都恰好有两个子结点,则称为满二叉树。
如果二叉树中除最后一层外其余层都是满的,并且最后一层的叶子是从左向右填满,则称为完全二叉树。
含有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);
}
} |
二叉树结点的接口
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 );
}
}
|