树 Tree
1.树 Tree 定义 树是层次化的而非线性的。 树是由显示结点间关系的边(edge)相联而成的结点(node)集合。 如果树的每个结点都可以有任意数目子结点,则称为一般树。 如果树中每个结点的子结点数目不超过n,则称为n叉树。 如果树中每个结点只有两个子结点,则称为二叉树。 从根开始,沿着连接结点的边从一个结点到另一结点,构成一条路径(path),顺着路径可以到达树中任何一个结点。根和其他任何一个结点之间的路径是唯一的。 二叉树 如果二叉树中的每个叶子结点都恰好有两个子结点,则称为满二叉树。 如果二叉树中除最后一层外其余层都是满的,并且最后一层的叶子是从左向右填满,则称为完全二叉树。 树的Java接口 public interface TreeInterface<T> { public T getRootData(); public int getHieght(); public int getNumberOfNodes(); public boolean isEmpty(); public void clear(); } 树的遍历方法接口 public interface TreeIteratorInterface<T> { public Iterator<T> getPerorderIterator(); public Iterator<T> getPostorderIterator(); public Iterator<T> getInorderIterator(); public Iterator<T> getLevelOrderIterator(); } 二叉树的接口 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); } 二叉树的实现 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的对象并且每个结点含有的对象不小于(或不大于)其后代中的对象的完全二叉树。在最大堆中,结点中的对象大于等于其后代对象。在最小堆中,结点的对象小于等于其后代对象。 最大堆的接口 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(); } 优先队列 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. 二叉树的结点 二叉树结点的接口 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的实现 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.com ” ©著作权归作者所有 |
