JZTXT

数据结构之树（二叉树的存储方式）

发布时间 2023-11-02 00:35:29作者: Allen_Hao

存储方式

一般使用数组、链表来存储树（节点）。链表的优点就是添加、删除。数组优点是访问（遍历）。

一维数组表示法

首先将二叉树当作一颗满二叉树（Full Binary Tree），因此第K层具有2k-1  个节点。按照规则存放在一维数组中。

原理

  • 对于一个具有n个节点的二叉树，可以使用一个长度为2n的数组来表示它。通常，数组的索引从0开始。
    • 对于数组中的任意索引 i，如果 i 处的元素表示二叉树的一个节点，那么：
    • 节点i的左子节点将位于索引 2i + 1的位置。
    • 节点i的右子节点将位于索引 2i + 2的位置。
    • 节点i的父节点将位于索引 (i - 1) / 2的位置（如果i不是根节点）。

最佳实践

  1. 在数组中表示二叉树时，确保数组的大小足够以容纳树中的所有节点。通常情况下，您需要知道树的大小（节点数）以便创建正确大小的数组。

  2. 当使用数组表示树时，树的结构通常是静态的，即不支持插入或删除节点。如果需要经常进行插入和删除操作，使用链表表示法可能更合适。

  3. 当数组表示的二叉树是满二叉树时（每个层级都是满的），效果最好。如果树是完全二叉树，效果也不错，但如果树的形状不规则，可能会浪费一些空间。

示例

public class ArrayBinaryTree {
    private int[] treeArray;

    public ArrayBinaryTree(int size) {
        treeArray = new int[size];
    }

    public int find(int value) {
        for (int i = 0; i < treeArray.length; i++) {
            if (treeArray[i] == value) {
                return i;
            }
        }
        return -1;
    }

    public void insert(int value) {
        for (int i = 0; i < treeArray.length; i++) {
            if (treeArray[i] == 0) {
                treeArray[i] = value;
                return;
            }
        }
    }

    public void preOrderTraversal(int index) {
        if (index >= treeArray.length || treeArray[index] == 0) {
            return;
        }
        System.out.print(treeArray[index] + " ");
        preOrderTraversal(2 * index + 1); // 左子节点
        preOrderTraversal(2 * index + 2); // 右子节点
    }

    public static void main(String[] args) {
        // 构建数组其实就是构建树（数组索引与树的左右子节点、父节点有关系）
        ArrayBinaryTree tree = new ArrayBinaryTree(10);
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(5);
        // 打印树结构，元素为0的表示是空节点即不存在的节点（空间浪费哦）
        System.out.println("Tree structure:");
        for (int value : tree.treeArray) {
            System.out.print(value + " ");
        }
        // 查找元素
        System.out.println("\nFind value 3 at index: " + tree.find(3));
        // 前序排序
        System.out.println("Pre-order traversal:");
        tree.preOrderTraversal(0);
    }
}

输出：

Tree structure:
1 2 3 4 5 0 0 0 0 0 
Find value 3 at index: 2
Pre-order traversal:
1 2 4 5 3