05、如何存储二叉树
大约 3 分钟数据结构算法基础面试题解析二叉树程序厨校招社招
如何存储二叉树
二叉树多采用两种方法进行存储,基于数组的顺序存储法和基于指针的二叉链式存储法
我们在之前说过的堆排序中,其中对堆的存储采用的则是顺序存储法,具体细节可以看这篇文章
这里我们再来回顾一下如何用数组存储完全二叉树.
-20251102155749865.(null))
我们首先看根节点，也就是值为 1 的节点，它在数组中的下标为 1 ,它的左子节点，也就是值为 4 的节点，此时索引为 2，右子节点也就是值为 2 的节点，它的索引为 3。
我们发现其中的关系了吗？
数组中，某节点（非叶子节点）的下标为 i , 那么其左子节点下标为 2*i （这里可以直接通过相乘得到左孩子, 也就是为什么空出第一个位置, 如果从 0 开始存，则需要 2i+1 才行）, 右子节点为 2i+1，其父节点为 i/2 。既然我们完全可以根据索引找到某节点的 左子节点 和 右子节点，那么我们用数组存储是完全没有问题的。
但是,我们再考虑一下这种情景,如果我们用数组存储斜树时会出现什么情况?
-20251102155754036.(null))
通过 2*i 进行存储左子节点的话,如果遇到斜树时,则会浪费很多的存储空间,这样显然是不合适的,
所以说当存储完全二叉树时,我们用数组存储,无疑是最省内存的，但是存储斜树时，则就不太合适。
所以我们下面介绍一下另一种存储结构,链式存储结构.
因为二叉树的每个节点, 最多有两个孩子, 所以我们只需为每个节点定义一个数据域,两个指针域即可
val 为节点的值, left 指向左子节点, right 指向右子节点.
-20251102155802786.(null))
下面我们对树 1, 2, 3, 4, 5, 6, 7 使用链式存储结构进行存储,即为下面这种情况.
-20251102155806309.(null))
二叉链表的节点结构定义代码
public class BinaryTree {
int val;
BinaryTree left;
BinaryTree right;
BinaryTree() {}
BinaryTree(int val) { this.val = val; }
BinaryTree(int val, BinaryTree left, BinaryTree right) {
this.val = val;
this.left = left;
this.right = right;
}
}
另外我们在刷题的时候, 可以自己实现一下数据结构, 加深我们的理解, 提升基本功, 而且面试考的也越来越多.
