如何编写自己的数组和列表

Question

我必须对几种不同类型的二叉树进行编程。但是，我不允许使用数组或集合等实用程序。如果需要的话，建议构建我自己的阵列。问题是，我什至不知道从哪里开始。比如说，我如何构建一个二维数组？

Answer 1

您必须通过创建对象来手动创建链接列表或树，每个对象都包含指向列表或树中下一个对象的指针。这是我上学时在数据结构课上做过很多次的练习。了解如何通过插入和删除来保持列表或树完整是一个有用的练习。

public class ListNode<T> {
  private T payload;
  private ListNode<T> nextNode;
}

public class TreeNode<T> {
  private T payload;
  private TreeNode<T> leftChild, rightChild;
}

Answer 2

您不需要数组来构建树。如果您在维基百科上找不到所需的内容，有几本关于算法和数据结构的书籍：

http:// en.wikipedia.org/wiki/Binary_tree

或 http://en.wikipedia.org/wiki/List_of_data_structs

（问题的答案：对于二维数组，创建一个一维数组，并将一维数组存储在一个一维数组中。这是可能的通过创建自己的链表实现来模拟内置数组，但这既不高效，也不符合您的老师的想法。）

（实际问题的灵感，你不知道自己是
询问：

类似这样的东西是二分搜索的核心数据结构
树...

类节点 {
     对象价值；
     节点向左；
     节点右；
} )

Answer 3

带有链表。这里的代码： http://www.roseindia.net/java/jdk6/LinkedListExample.shtml

Answer 4

编辑：好吧，每个人都提到了列表，但我们不要忘记，您也可以在数组上实现二叉树，就像实现堆一样。所以我们有这样的东西：

public class BinaryTree {
    private int[] tree; // assuming each node holds an integer.
    private int nodeCount;

    public BinaryTree (int nodes) {
         tree = new int[nodes * 2];
         nodeCount = nodes;
    }

    public int getRoot() {
         return tree[0];
    }

    private int getPositionOfNode(int value) {
         for(int i = 0; i < nodeCount; i++) {
             if(tree[i] == value) {
                 return i;
             }
         }
         return -1;
    }

    public int getLeftChildOfNode(int node) {
         int pos = getPositionOfNode(node);
         if(pos != -1) {
              return tree[pos * 2];
         }
         return pos;
    }

    public int getRightChildOfNode(int node) {
         int pos = getPositionOfNode(node);
         if(pos != -1) {
              return tree[pos * 2 + 1];
         }
         return pos;
    }

    public int getParentOfNode(int node) {
         int pos = getPositionOfNode(node);
         if(pos != -1) {
              return tree[pos / 2];
         }
         return pos;
    }
}

在这个结构中，如果一个节点位于位置 i，它的子节点将位于位置 2*i 和 2*i+1。

Answer 5

public class TwoDArray {
   private Object[] values;
   public TwoDArray(int n, int m) {
       values = new Object[n * m];
   }
   public void set(int i, int j, Object x) { ... }
   public Object get(int i, int j) { ... }
}
public class BinTree {
   private BinTree left;
   private BinTree right;
   private Comparable value;
   public void insert(Comparable x) { ... }
}

像这样的东西吗？
应该没那么难。

Answer 6

首先，我假设您甚至被禁止使用 Java 的原始数组类型。在这种情况下，您将不得不回到最基础的知识并开始自己管理内存。您需要首先分配适当大小的字节数组或 ByteBuffer。然后，将使用 C 语言中简单的指针数学来处理对该数据块的访问。

16 个 int 的一维数组示例：

byte[] mem = new byte[16 * 4] ; // Ints are 4 bytes long

// Write a value to the 8th element of our "array"
index = 8 ;
int value = 31415926 ;
mem[4 * index + 0] = (byte)( value >> 24 ) ;
mem[4 * index + 1] = (byte)( ( value << 8 ) >> 24 ) ;
mem[4 * index + 2] = (byte)( ( value << 16 ) >> 24 ) ;
mem[4 * index + 3] = (byte)( ( value << 24 ) >> 24 ) ;

通过反转该过程并计算存储的 int 值来读取值。

注意：使用 ByteBuffer 设置和检索值的过程更容易，因为它是获取原始 Java 类型并将其放入字节数组的方法。