将二叉树转换为对应的无向图

Question

给定一个二叉树的表示，它最多可以有 n 个节点：

typedef struct node
{
  int info,n;
  struct node *left,*right;
}tree_node;

从最多有n个节点的二叉树构造一个无向图

图表示为结构：

typedef struct
{
  int n;
  tree_node *nodes[];
  int adjacency_m[][];
}graph;

我们可以使用 Prim、Kruskal 或 DFS[=29= 等算法从图中得到一棵树].

问题：有没有一种算法可以从二叉树创建图？例如，如果以 In-order 方式遍历二叉树，那么如何从中创建无向图？

Answer 1

假设您已经实现了图形结构和向图形添加边的函数，我将以 C 方式解决您的问题 void add(int a, int b)。此外（为简洁起见）我假设你的图有一个静态全局变量，它至少有一些节点深（我跳过了角落案例，对你来说更有趣）。

void tree_to_graph(tree_node *node) {
    if (node->left != NULL) {
        add(n, node->left->n);
        tree_to_graph(node->left);
    }
    if (node->right != NULL) {
        add(n, node->right->n);
        tree_to_graph(node->right);
    }
}

极端情况是图不够深。你应该实施这个案例。 add 函数应在图表中添加一条从 a 到 b 的边。您还应该添加一个向节点添加信息的函数，但我的代码应该是必要的最低限度工作，将有趣的部分留给您。

Answer 2

我有点惊讶你知道中序遍历，但不能自己解决这个问题。我给你一个基本的大纲：

我假设 tree_node 中的 info 成员是节点 ID。

您必须执行以下操作：

1) 初始化您的数据结构，即为所有 i,j、0 <= i < n、0 <= j < n

设置 adjacency_m[i][j] = 0

2) 在你的中序遍历中，当你访问一个节点时：

tree_to_graph(tree_node *node) {
     // add a pointer to the node
     graph->nodes[node->info] = node;

     if(node->left) {
          // if node has a left child, , add adjecancy matrix entries for edges from node -> left, and left -> node
          graph->adjacency_m[node->info][node->left->info] = 1;
          graph->adjacency_m[node->left->info][node->info] = 1;
          tree_to_graph(node->left);
     }
     if(node->right) {
          // if node has a right child, add adjecancy matrix entries for edges from node -> right, and right-> node
          graph->adjacency_m[node->info][node->right->info] = 1;
          graph->adjacency_m[node->right->info][node->info] = 1;
          tree_to_graph(node->right);
     }

 }

编辑： 从评论中的讨论可以看出，您的问题不是很清楚。您应该区分树和用于表示它们的图形和数据结构的抽象数学概念。正如您所说的那样，BFS、Kruskal 和 Prim 可用于计算图形的生成树。正如评论中所讨论的那样，根据定义，任何树都是图。图通常用邻接矩阵表示，而二叉树通常用递归树结构表示。请注意，您也可以用邻接矩阵表示二叉树（如有必要，您可以使用不同的邻接值对 "left" 和 "right" 子信息进行编码，例如 1 和 2），以及一个图具有这样的递归树状结构（尽管对于一般图形，您必须允许两个以上的传出边）。在您的问题中，您询问的是将二叉树的表示形式从类树递归结构转换为邻接矩阵。

将二叉树转换为对应的无向图

Convert a binary tree to corresponding undirected graph

c

algorithm

binary-tree

undirected-graph