ufo - 1 year ago 68

C Question

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

Graph is represented as a struct:

`typedef struct`

{

int n;

tree_node *nodes[];

int adjacency_m[][];

}graph;

We can get a tree from graph by using algorithms like

For example, if binary tree is traversed in

Answer Source

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;
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);
}
}
```

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