Блог

Главная - Вопросы по программированию - Как напечатать тренарное дерево в BFS?

Как напечатать тренарное дерево в BFS?

#c

#c

Вопрос:

у меня есть обучающее дерево:

 typedef struct Trin_Ari {
int id;
char* name;
struct Trin_Ari *parent;
struct Trin_Ari *left;
struct Trin_Ari *middle;
struct Trin_Ari *right;
}Trin_Ari;

у меня есть участники в таком порядке:
введите описание изображения здесь

и мне нужно распечатать их таким образом:

 A1
B2
D4
G7
C3
E5
F6
H8
I9

Комментарии:

1. Примечание: на чертеже отсутствуют узлы G, H, I .

2. Вы спрашиваете конкретно о троичных деревьях. Знаете ли вы о том, как это делать в двоичных деревьях? С каким препятствием вы сталкиваетесь при попытке. Я спрашиваю, потому что ваш вопрос не демонстрирует никаких собственных усилий и, похоже, просто запрашивает код. Также неясно, какой уровень детализации вам нужен, с нуля, кажется, из-за того, что ничего не демонстрирует, но заголовок явно фокусируется на троичных деревьях….

Ответ №1:

Обход дерева порядка уровней.

  • начните с корневого узла
  • для каждого узла
    • печать данных узла
    • поместите дочерние элементы (если они есть) в очередь (в очередь — слева направо)
    • возьмите следующий элемент из очереди (удаление из очереди)

Пример кода:

 // for test purpose
#define MAX_NODES 32

static struct {
    int head, tail;
    Trin_Ari* data[MAX_NODES]; // or allocate at runtime
} queue;

static void reset_queue()
{
    queue.head = queue.tail = 0;
    memset(queue.data, 0, sizeof(Trin_Ari*) * MAX_NODES);
}

static void enqueue(Trin_Ari *node)
{
    queue.data[queue.tail  ] = node;
}

static Trin_Ari* dequeue()
{
    return queue.data[queue.head  ];
}

void print(Trin_Ari *root)
{
    Trin_Ari *node = root;
    reset_queue();
    
    while (node) {

        // print node data
        printf("%i, %sn", node->id, node->name);

        // enqueue child nodes
        if (node->left)   enqueue(node->left);
        if (node->middle) enqueue(node->middle);
        if (node->right)  enqueue(node->right);
        
        // dequeue a node from the queue
        node = dequeue();
        
    }
}

Для дерева:

             A
    /       |       
   B        C        D
 / |     / |     / | 
E  F  G  H  I  J  K  L  M

1. Итерация

  • печать: A
  • очередь: B C D // в очереди
  • узел: B // удален из очереди

2. Итерация

  • печать: B
  • очередь: B C D E F G
  • узел: C

3. Итерация

  • печать: C
  • очередь: B C D E F G H I J
  • узел: D

4. Итерация

  • печать: D
  • очередь: B C D E F G H I J K L M
  • узел: E

5. Итерация

  • печать: E
  • очередь: B C D E F G H I J K L M //<- без изменений, поскольку E..M являются листьями (без дочерних элементов)
  • узел: F

Итерация будет продолжаться до узла M (последнего элемента в очереди).