数据结构中的二叉树表示

我们将了解如何在计算机内存中表示二叉树。有两种不同的表示方法：使用数组和使用链表。

假设我们有一棵这样的树：

数组表示法通过使用层序遍历扫描元素来存储树数据。因此它逐层存储节点。如果某些元素缺失，则为其保留空白空间。上述树的表示如下：

索引1保存根节点，它有两个子节点5和16，它们分别位于位置2和3。一些子节点缺失，因此它们的位置留空。

在此表示中，我们可以使用以下公式轻松获得一个节点的两个子节点的位置：

$$child_{1}=2*parent$$ 

$$child_{2}=\lgroup2*parent\rgroup+1$$

要从子节点获取父节点索引，我们必须遵循以下公式：

$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$

这种方法很好，我们可以很容易地找到父节点和子节点的索引，但它不是内存高效的。它将占用许多无用的空间。这种表示对于完全二叉树或满二叉树是合适的。

另一种方法是使用链表。我们为每个元素创建一个节点。这将如下所示：

Arnab Chakraborty

更新于：2019年8月27日

15K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始学习