请问二叉树等数据结构的物理存储结构是怎样的？-轻识

走过路过不要错过

点击蓝字关注我们

请问二叉树等数据结构的物理存储结构是怎样的？

好吧，咱们书上说了，一般两种存储方式: 1. 以完全二叉树的形式用连续空间的数组存储; 2. 以链表形式存储,即各个数据之间保存了相关的数据的指针地址！
如果回答就是这样，那么我想大家也不费那神了，直接洗洗睡吧？咱们能不能深入点？

数组是好理解的，在内存在磁盘都是一样的，连续相邻的空间，挨着存放到磁盘就可以了；好吧，就算你正确？那么链表呢？拿简单的单链表来说，上一个节点保存下一个节点的指针？是如何保存的？我们能想到的，就是一个上一节点存储了下一节点的绝对地址或者偏移地址，好像是这样的！

那么问题来了，这个下一节点地址到底是什么样的呢？是相对地址还是绝对地址？这个地址是怎么算出来的？存储在内存上是肯定没有问题的！但是如果存储在磁盘上呢？如果这个地址是固定的，那么，如果换了硬盘（换了存储介质），是否就找不到该地址（因为每个设备的地址自然是不一样的）？

针对这个问题，很是困扰了我很久！也询问过几个身边的小伙伴，也都说不知道。后来在一次面试中，一面试官刚好问我这问题，我把自己的见解说完后，说我确实不知道是怎么存储的。最后我要求他给予答案，然后，他说，就是存储的下一节点的地址（内存地址），压根不存在什么数据结构存储于磁盘这种说法，内存中，是动态计算的值。如果存在内存拷贝，那么，也会重新计算这些地址的，所以看起来相同的结构，在不同存储工具上，会会表现出不同的地址空间。

好吧，我将信将疑！被丢了n个鄙视的表情，然后被pass掉了。

那么，到底内存中的二叉树怎么存储在硬盘上的呢？

其实硬盘上并没有什么二叉树的，硬盘只是充当了一个存储介质，只是提供你要读的时候可以取而已，而真正的数据结构，则需要在用的时候再还原出原来的树形结构！

下面以一个简单的示例来展示磁盘上的数据结构的存储方式:

public class BinTreeDiskSample {    private static int h = -1;    private static Node root;    static class Node implements Serializable {        private static final long serialVersionUID = -4780741633734920991L;        int data;        transient Node left;        transient Node right;        int lHeight = -1, rHeight = -1;        public Node(int data) {            this.data = data;        }        public Node setLeft(Node left) {            this.left = left;            return this;        }        public Node setRight(Node right) {            this.right = right;            return this;        }        public Node getLeft() {            return left;        }        public Node getRight() {            return right;        }        // 后续遍历写入，先序遍历读出        public int write(ObjectOutputStream out) throws IOException {            if (left != null) {                lHeight = left.write(out);            }            if (right != null) {                rHeight = right.write(out);            }            h++;            out.writeObject(this);            return h;        }        private void init(List<Node> list) {            if (lHeight != -1) {                left = list.get(lHeight);                left.init(list);            }            if (rHeight != -1) {                right = list.get(rHeight);                right.init(list);            }        }
    }    public static void binTreePreOrderPrint(Node root) {        System.out.print(root.data + " ");      // visit root        if(root.left != null) {            binTreePreOrderPrint(root.left);        }        if(root.right != null) {            binTreePreOrderPrint(root.right);        }    }    // 先序遍历读出    public static void read(ObjectInputStream in) throws IOException,            ClassNotFoundException {        List<Node> list = new ArrayList<Node>();        Node n;        Object obj;        try {            while ((obj = in.readObject()) != null) {                n = (Node) obj;                list.add(n);            }        }        catch (Exception e) {            // EOFException ...//            e.printStackTrace();        }        root = list.get(list.size() - 1);        root.init(list);    }    public static void main(String args[]) throws FileNotFoundException,            IOException, ClassNotFoundException {        // 构造一棵二叉树 11 21 41 61 51 31        Node n6 = new Node(61);        Node n4 = new Node(41).setLeft(n6);        Node n5 = new Node(51);        Node n2 = new Node(21).setLeft(n4).setRight(n5);        Node n3 = new Node(31);        Node n1 = new Node(11).setLeft(n2).setRight(n3);        root = n1;        System.out.println("output node: ");        binTreePreOrderPrint(root);        // 将数据写稿磁盘        ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("btree.bin"));        root.write(out);        out.close();
        root = null;        // 将数据从磁盘读入，并进行数据结构的重新构建        ObjectInputStream in = new ObjectInputStream(new FileInputStream("btree.bin"));        read(in);        in.close();        System.out.println("\nread node: ");        binTreePreOrderPrint(root);    }
}