0

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

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

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

Graph 表示为一个结构：

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

我们可以使用Prim、Kruskal或DFS等算法从图中得到一棵树。

问题：有没有一种算法可以从二叉树创建图？例如，如果按顺序遍历二叉树，那么如何从中创建无向图？

4

2 回答 2

6

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

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

您必须执行以下操作：

1) 初始化您的数据结构，即为adjacency_m[i][j] = 0所有i,j, 0 <= i < n, 设置0 <= j < n

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 可用于计算图的生成树。正如评论中所讨论的，任何树都是定义的图。图通常用邻接矩阵表示，而二叉树通常用递归树结构表示。请注意，您也可以用邻接矩阵表示二叉树（如有必要，您可以使用不同的邻接值对“左”和“右”子信息进行编码，例如 1 和 2），以及具有这种递归的图树状结构（虽然对于一般图，你' 必须允许两个以上的出边）。在您的问题中，您问的是如何将二叉树的表示从树状递归结构转换为邻接矩阵。

于 2016-09-06T07:23:02.773 回答
2

假设您已经实现了图形结构和用于向图形添加边的函数，我将以 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函数应该在您的图表中添加一条边 from ato 。b您还应该添加一个向节点添加信息的函数，但我的代码应该是必要的工作最低限度，把有趣的部分留给您。

于 2016-09-06T07:19:10.140 回答