树 Tree
您目前处于:编程  2013年06月22日

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 ”