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

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等算法从图中获取树.

问题:是否存在从二叉树创建图形的算法？例如,如果以顺序方式遍历二叉树,那么如何从中创建无向图？

Answer 1

我对您了解有序遍历感到有些惊讶,但无法自行解决这个问题.我会给你一个基本的大纲:

我假设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)对"左"和"右"子信息进行编码),以及具有这种递归的图形树状结构(虽然对于一般图形,您将不得不允许两个以上的传出边缘).在您的问题中,您要问的是将二叉树的表示从树状递归结构转换为邻接矩阵.