ufo ufo - 7 months ago 36
C Question

Convert a binary tree to corresponding undirected graph

Given a representation of a binary tree which can have the maximum of n nodes:

typedef struct node
int info,n;
struct node *left,*right;

Construct an undirected graph from a binary tree which can have the maximum of n nodes.

Graph is represented as a struct:

typedef struct
int n;
tree_node *nodes[];
int adjacency_m[][];

We can get a tree from graph by using algorithms like Prim, Kruskal or DFS.

Question: Is there an algorithm that creates a graph from a binary tree?
For example, if binary tree is traversed in In-order fashion, then how to create an undirected graph from it?


I'm a bit surprised that you know about in-order traversal, but cannot solve this on your own. I'll give you a basic outline:

I'm assuming that the info member in your tree_node is the node id.

You have to do the following:

1) Initialize your data structures, i.e., set adjacency_m[i][j] = 0 for all i,j, 0 <= i < n, 0 <= j < n

2) In your in-order traversal, when you visit a node:

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;
     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;


Edit: As you can see by the discussion in the comments, your question wasn't really clear. You should distingiush between the abstract, mathematical concepts of a tree and a graph and data structures used to represent them. As you say correctly, BFS, Kruskal and Prim can be used to compute a spanning tree of a graph. As disussed in the comments, any tree is a graph by definition. A graph is often represented with an adjacency matrix, wheras a binary tree is often represented with a recrusive tree-structure. Note that you may as well represent a binary tree with an adjacency matrix (if necessary, you can encode the "left" and "right" child information with different adjacency values, e.g., 1 and 2), and a graph with such a recursive tree-like structure (although for a general graph, you'll have to allow for more than two outgoing edges). In your question, you are asking about converting the representation of a binary tree from a tree-like recursive structure to an adjacency matrix.