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;

我们可以使用PrimKruskalDFS等算法从图中得到一棵树。

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

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 回答