data-structures - 我们可以用单链表构造一棵二叉树吗

Question

我搜索了很多，但没有一个显示如何使用单链表创建二叉树。甚至可以创建一个？！我记得我在某处读过可以使用单链表创建二叉树。

Answer 1

您可以将二叉树表示为数组。如果你想在你的树中唯一的方向是从根到叶，那么理论上你可以使用单链表而不是数组。

但是，这将导致巨大的性能损失，因为您将不得不进行指针追逐，而不是像在数组中那样直接跳转到下一个节点。

我发现很难想到你会真正做到这一点的场景，但原则上它是可能的。