ufo - 2 months ago 11
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;
}tree_node;
``````

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[];
}graph;
``````

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