握手引理和有趣的树属性 - DSA

在本教程中，我们将学习 DSA 中的握手引理和一些有趣的树的性质。

握手引理究竟是什么？

握手引理是关于无向图的。在每个有限的无向网络中，具有奇数度数的顶点的数量总是偶数。（度数和公式是握手引理的来源，它也经常被称为握手引理）。

握手引理如何帮助树数据结构？

握手引理可用于证明以下令人惊叹的事实。

1) 在二叉树中，叶子节点的数量总是比有两个子节点的节点的数量多一个。

L = T + 1

L 是叶子节点的数量。

T 表示有两个子节点的内部节点的数量。

证明

令 T 表示有两个子节点的节点的数量。证明分为三种类型。

情况 1：因为只有一个节点，所以 T = 0 L = 1 的关系成立。

情况 2：根有两个子节点，这意味着根的度数为二。

情况 3：根有一个子节点，因此根的度数为一。

因此，在所有三种情况下都可以得到 T = L-1。让我们看另一个有趣的特性。

2) 无论节点有 0 个子节点还是 k 个子节点，k 叉树中的以下性质都成立。

L = (k - 1)*I + 1，其中 L 是叶子节点的数量。

I 表示内部节点的数量。

证明分为两种类型。

情况 1（根是叶子）：树只有一个节点。对于单个节点，前面的表达式有效，因为 L = 1，I = 0。

情况 2（根是内部节点）：在具有一个以上节点的树中，根总是内部节点。在这种情况下，可以使用握手引理来验证上述表达式。无环无向图就是一棵树。

树中边的总数等于节点数减一，即 |E| = L + I - 1。

除了根节点之外，指定类型树中的所有内部节点的度数均为 k + 1。根节点的度数为 k。所有叶子节点的度数均为一。将握手引理应用于这些树会得到以下关系。

因此，上述性质已通过握手引理得到证明。