c - 编辑我的代码以了解输入是否是二叉树

Question

我有一个程序，它接受邻接矩阵作为输入，然后计算相应的图是否是树。我想修改它，以便它确定该图是否是特定的二元树，但我真的无法理解它。我需要做什么？

原始代码如下:

#include<stdio.h>
#include<stdlib.h>

int A[20][20]; // Our two-dimensional array.
int visited[20];
int v = 0;
int count = 0;
int n;
int seq[20];
int s = 0;
int connected = 1;
int acyclic = 1;

// Declaration of the DFS function
void DFS();

// Declaration of the DFSearch function
void DFSearch(int cur);

int main() {
    int i,j;

    printf("\nStep 1 of 2 — Fill in your desired number of vertices: ");
    scanf("%d",&n);

    printf("\nStep 2 of 2 — Fill in the adjacency matrix(1/0):\n");

    for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
        scanf("%d",&A[i][j]);
        }
    }

    printf("\nThe DFS traversal shows:\n");

    DFS();

    for(i=1; i<=n; i++) {
        printf("%c,%d\t", 'a'+seq[i]-1, i);
    }

    if(connected && acyclic) {
            printf("\n\nThis is a connected and non-cyclic graph. Therefore, it IS a tree.");
    }

    if(!connected && acyclic) {
            printf("\n\nThis is a non-connected and non-cyclic graph. Therefore, it is NOT a tree.");
    }

    if(connected && !acyclic) {
        printf("\n\nThis is a connected and cyclic graph. Therefore, it is NOT a tree.");
    }

    if(!connected && !acyclic) {
            printf("\n\nThis is a non-connected and cyclic graph. Therefore, it is NOT a tree.");
    }
    printf("\n\n");
    return 0;
}

// Definition of the DFS function
void DFS() {
    int i;

    for(i=1; i<=n; i++) {
        if(!visited[i]) {
                if(i>1) {
                    connected = 0;
                    DFSearch(i);
                }
        }
    }
}

// Definition of the DFSearch function
void DFSearch(int cur) {
    int i,j;

    visited[cur]=++count;

    seq[count]=cur;

    for(i=1; i<count-1; i++) {
            if(A[cur][seq[i]]) {
                acyclic = 0;
            }
    }

    for(i=1; i<=n; i++) {
        if(A[cur][i] && !visited[i]) {
           DFSearch(i);
        }
    }
}

Answer 1

二叉树与其他树有何区别？想必您知道，正是没有一个节点具有超过一个父节点或两个以上子节点。当然，区分父节点和子节点需要一个有向图，或者至少是一个有序图。这与树是非循环的一般属性相结合，意味着二叉树也是 Root过的。

现在，有向图自然受到您正在使用的邻接矩阵表示的支持，所以这没有问题。事实上，邻接矩阵表示对于无向图来说有点不自然，但是您可以通过将它们表示为对称邻接矩阵来很好地服务这些。

遵循程序的范例，然后，我建议添加一个变量

int binary = 1;

并在检查每个节点时测试该节点是否具有两个以上的传出边(因此，是否有两个以上的子节点)。如果找到一个节点，则将变量设置为零，表明虽然该图可能是一棵树，但它不是二元树。

当然，要做到这一点需要充分分析程序以了解其工作原理。我不会剥夺您宝贵的经验，但也许我指出该计划比问题所暗示的更具体一点会对我有所帮助。它通常不计算提供的邻接矩阵是否对应于树，而是计算矩阵是否对应，

• 解释为有向图的表示，
• 对应于以第一个节点为根的树。