Преобразование двоичного дерева в соответствующие неориентированный граф

Question

Учитывая представление двоичного дерева, которое может иметь максимум п узлов:

typedef struct node 
{ 
    int info,n; 
    struct node *left,*right; 
}tree_node; 

Построить неориентированный граф из двоичного дерева, которое может иметь максимум n узлов.

График представлен в виде структуры:

typedef struct 
{ 
    int n; 
    tree_node *nodes[]; 
    int adjacency_m[][]; 
}graph; 

Мы можем получить дерево из графа с использованием алгоритмов как Прима, Крускала или ДФС.

Вопрос: Есть ли алгоритм, который создает граф из двоичного дерева? Например, если бинарное дерево пересекается в В порядке способа, то как создать неориентированный граф?

Answer 1

Я немного удивлен, что вы знаете об обходном порядке, но не можете решить это самостоятельно. Я дам вам базовый план:

Я предполагаю, что член info в вашем tree_node является идентификатором узла.

Вы должны сделать следующее:

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

} 

Edit: Как вы можете видеть на обсуждение в комментариях, ваш вопрос был не совсем понятно. Вы должны дистанцироваться между абстрактными, математическими концепциями дерева и графом и структурами данных, которые используются для их представления. Как вы правильно говорите, BFS, Kruskal и Prim могут использоваться для вычисления остовного дерева графика. Как объяснено в комментариях, любое дерево является графиком по определению. Граф часто представлен матрицей смежности, поскольку двоичное дерево часто представлено с помощью рекруссивной древовидной структуры. Обратите внимание, что вы можете также представлять двоичное дерево с матрицей смежности (при необходимости вы можете кодировать «левую» и «правую» дочернюю информацию с разными значениями смежности, например, 1 и 2), и график с такой рекурсивной древовидной структуры (хотя для общего графика вам нужно будет иметь более двух исходящих ребер).В вашем вопросе вы спрашиваете о преобразовании представления двоичного дерева из древовидной рекурсивной структуры в матрицу смежности.

Answer 2

Я разрешу ваш вопрос с учётом того, что вы внедрили структуру графа и функцию для добавления ребер к вашему графику 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 необходимо добавить кромку от a до b. Вы также должны добавить функцию, которая добавляет информацию в узел, но мой код должен был быть необходимым рабочим минимумом, оставив вам интересную часть.