二叉树的实现方式

Question

4

以下是有关算法书籍的摘录。

我们可以使用矩形框来绘制二叉树，但通常情况下，由于它们实际上是图形，所以树被绘制为由线连接的圆圈。当涉及到树时，我们也不会明确绘制NULL链接，因为每个具有N个节点的二叉树都需要N+1个NULL链接。

我的问题是，作者的意思是什么，每个具有N个节点的二叉树都需要N+1个null链接？作者如何得出N+1这个数字？

- venkysmarty

3

自己试一试，画一个有1个节点（2个空节点），2个节点（3个空节点），3个节点（4个空节点）等的树。你已经做过了吗？如果是的话，如果你还是卡住了，我们可以向您展示归纳规则。这并不难。 - Ray Toal

从另一个角度看，每个有N个节点的二叉树有N-1个非空链接（可以画一些树来自己看看）。由于每个节点有2个链接，你会得到（2N - （N-1））= N + 1个空链接。 - comingstorm

3个回答

4

您可以通过数学归纳法证明这一点。

1个节点有2个NULL链接-满足该属性。

现在假设所有具有n-1个节点的树都有n个NULL链接。然后我们希望展示，所有具有n个节点的树都有n+1个NULL链接。

取任意具有n个节点的树，并选择其中一个叶子节点。移除此叶子节点。现在我们有一棵具有n个NULL链接的树，符合我们的假设。如果我们再次添加叶子节点，则会失去一个NULL链接，但获得两个。因此，具有n个节点的树上有n-1+2=n+1个NULL链接。

- Sebastian Paaske Tørholm

1

观察：每条边都充当链接。N个节点需要N-1条边。

总链接数：2N。

空链接数：2N - (N-1) = N+1。

- RobinSun

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Larsen · Accepted Answer

如果你有一个仅包含1个节点的树，那么该节点会有两个空链接（左链接和右链接）。如果你在左侧或右侧添加一个节点，那么你将填充1个空链接并添加2个链接。这种情况将无限继续下去，因此每添加一个节点，你就会多出1个额外的空链接。