用图遍历来检验图是不是完美二叉树

Question

当给定一个由邻接表表示的无向图 G 时，如何使用 DFS 来查看该图是否是完美二叉树？

我已经能够识别边缘情况：例如使用深度 D 需要 2^n-1 个节点的事实，您可以使用对数计算出最大深度，如果这不是完整的你知道你没有完美的树，但我想不出使用邻接表和 DFS 进行测试的有效方法。

Answer 1

在一个非空的、有节点的完美二叉树中，我们有这些属性：

节点数比2的幂少1，即ℎ=log_₂(+1)为整数。 =2^ℎ−1
边数为−1
没有超过 3 个邻居的节点。
当 > 1 时，（只有）一个节点恰好有 2 个邻居：它是根。
当>1时，树的叶子只有一个邻居：有2^ℎ-1个。
根与任意叶子的距离为ℎ−1.

这些属性可以一个接一个地检查。一旦确定了根，就可以执行遍历来检查距离属性。使用 DFS 或 BFS。

Answer 2

如果图形为空，或只有一个顶点，则 return 为真。

否则，请检查以确保图是连通的并且是无环的。

那么，如果是一棵完全二叉树，那么一定只有一个2度的顶点，那就是根。让a和b成为它的两个children。那么：

let depthA = depthIfPerfect(a, root);
let depthB = depthIfPerfect(b, root);
return depthA == depthB && depthA >=0

其中：

depthIfPerfect(node, parent):

    if degree(node) == 1:
        return 1;
    if degree(node) != 3:
        return -1; //not perfect

    let a and b be the neighbors that aren't parent

    let depthA = depthIfPerfect(a, node);
    let depthB = depthIfPerfect(b, node);
    
    if (depthA != depthB || depthA < 0):
        return -1: //not perfect
    return depthA+1;

如果愿意，您可以将连通性和非循环性检查混合到此遍历中。

用图遍历来检验图是不是完美二叉树

Using graph traversal to test is a graph is a perfect binary tree

algorithm

binary-tree

graph-algorithm