Java 数据结构实现（DataStructure）2

摘要：堆栈可以看成是有特定规则为的线性表，特定规则就是先进后出，后进先出，可以看成是我们的先的要后，所以利用这一点可以通过继承或组合的方式来构建堆栈。鉴于上面这张物理结构和逻辑结构，我们采用提供的来构建主存储结构，即节点的线性表以达到索引的目的。

堆栈

可以看成是有特定规则为的线性表，特定规则就是先进后出，后进先出，可以看成是我们List的先insertFromHead的要后deleteFromHead，所以利用这一点可以通过继承或组合的方式来构建堆栈。

继承构建堆栈：

public class StackInheritance extends List {
   public StackInheritance() { super( "stack" ); }
   public void push( Object o )
      { insertFromHead( o ); }
   public Object pop() throws EmptyListException
      { return deleteFromHead(); }
   public boolean isEmpty() { return super.isEmpty(); }
   public void print() { super.print(); }
}

组合构建堆栈：

public class StackComposition {
   private List s;

   public StackComposition() { s = new List( "stack" ); }
   public void push( Object o )
      { s.insertFromHead( o ); }
   public Object pop() throws EmptyListException
      { return s.deleteFromHead(); }
   public boolean isEmpty() { return s.isEmpty(); }
   public void print() { s.print(); }
}

队列

可以看成是有特定规则为的线性表，特定规则就是先进先出（FIFO），后进后出，可以看成是我们List的先insertFromBack的要后deleteFromHead，所以利用这一点可以通过继承或组合的方式来构建堆栈。

继承构建队列

public class QueueInheritance extends List {
   public QueueInheritance() { super( "queue" ); }
   public void enqueue( Object o )
      { insertFromBack( o ); }
   public Object dequeue()
      throws EmptyListException { returnDeleteFromHead(); }
   public boolean isEmpty() { return super.isEmpty(); }
   public void print() { super.print(); }
}

二叉树

可以看成是一堆散节点通过特殊的连接构成的散点集，这些散点集构成了特殊的结构，看起来成了树一样的结果。

如下图所示，上面的为二叉树的逻辑结构，这样的逻辑结构利于分析二叉树的性质，却不能说明二叉树存储的实际情形，因此需要使用下图所示的二叉树的物理结构来描述其存储特性，二叉树的节点存储为线性表，线性表中的节点有自己的特殊的包含（连接关系），因此使得这种物理结构和它的逻辑结构有了能够转换的基础。

鉴于上面这张物理结构和逻辑结构，我们采用Java提供的List（LinkedList）来构建主存储结构，即Node节点的线性表以达到索引的目的。然后建立节点之间的连接关系。

import java.util.LinkedList;
import java.util.List;

public class BinTreeTraverse {

    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    private static List nodeList = null;

    /**
     * 内部类：节点
     */
    private static class Node {
        Node leftChild;
        Node rightChild;
        int data;

        Node(int newData) {
            leftChild = null;
            rightChild = null;
            data = newData;
        }
    }

    public void createBinTree() {
        nodeList = new LinkedList();
        // 将一个数组的值依次转换为Node节点
        for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
            nodeList.add(new Node(array[nodeIndex]));
        }
        // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
            // 左孩子
            nodeList.get(parentIndex).leftChild = nodeList
                    .get(parentIndex * 2 + 1);
            // 右孩子
            nodeList.get(parentIndex).rightChild = nodeList
                    .get(parentIndex * 2 + 2);
        }
        // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以多带带拿出来处理
        int lastParentIndex = array.length / 2 - 1;
        // 左孩子
        nodeList.get(lastParentIndex).leftChild = nodeList
                .get(lastParentIndex * 2 + 1);
        // 右孩子,如果数组的长度为奇数才建立右孩子
        if (array.length % 2 == 1) {
            nodeList.get(lastParentIndex).rightChild = nodeList
                    .get(lastParentIndex * 2 + 2);
        }
    }

    /**
     * 先序遍历
     * 
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
     * 
     * @param node
     *            遍历的节点
     */
    public static void preOrderTraverse(Node node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }

    /**
     * 中序遍历
     * 
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
     * 
     * @param node
     *            遍历的节点
     */
    public static void inOrderTraverse(Node node) {
        if (node == null)
            return;
        inOrderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        inOrderTraverse(node.rightChild);
    }

    /**
     * 后序遍历
     * 
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
     * 
     * @param node
     *            遍历的节点
     */
    public static void postOrderTraverse(Node node) {
        if (node == null)
            return;
        postOrderTraverse(node.leftChild);
        postOrderTraverse(node.rightChild);
        System.out.print(node.data + " ");
    }

    public static void main(String[] args) {
        BinTreeTraverse binTree = new BinTreeTraverse();
        binTree.createBinTree();
        // nodeList中第0个索引处的值即为根节点
        Node root = nodeList.get(0);

        System.out.println("先序遍历：");
        preOrderTraverse(root);
        System.out.println();

        System.out.println("中序遍历：");
        inOrderTraverse(root);
        System.out.println();

        System.out.println("后序遍历：");
        postOrderTraverse(root);
    }

}

  
这里我们为什么不使用自己定义的NodeList呢？因为如果一旦使用这个NodeList来作为主存储部分，就会使得在子节点的指向过程中导致整个结构指向混乱，造成对结构的破坏。