Как распечатать бинарное дерево по горизонтали? - PullRequest
Новая
       21

Как распечатать бинарное дерево по горизонтали?

3 голосов
/ 28 февраля 2020

Как я могу напечатать мое двоичное дерево таким образом? 

the original tree      I need 
      5                5
     /  \              
    2    9             2   9
   / \  / \   
  0  3  7  12          0 3 7 12

Моя функция печати: 

void display(struct node* start){
    cout << start->data << " ";
   if(start != NULL){
        if(start->left){
            cout << "\n";
           display(start->left);
    }
        if(start->right) {
            display(start->right);
        }
    }
}

В настоящее время моя функция печатает таким образом 

5
2 
0 3 9
7 12

Ответы [ 3 ]

3 голосов
/ 28 февраля 2020

Вы можете создать карту ha sh, чтобы указать уровень дерева, на котором вы находитесь, в соответствии со значениями на этом уровне дерева. Например: 

std::map<unsigned, std::vector<unsigned>> hash;

Затем вы можете go через ваше дерево и заполнить карту так, чтобы ваша карта выглядела так: 

hash[0] = { 5 };
hash[1] = { 2, 9 };
hash[2] = { 0, 3, 7, 12 };

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

for (unsigned i = 0; i < hash.size(); i++ ) { // each level of tree
    for (auto& v : hash[i] ) { // each element in that vector
        std::cout << v << " ";
    }
    std::cout << '\n';
}

Нечто подобное может быть одним из возможных решений ...

2 голосов
/ 28 февраля 2020

Проблема в том, что вы не можете печатать «назад». После того, как вы напечатали строку, вы не сможете go выполнить резервное копирование (используя стандартный C ++, это может быть возможно с использованием управляющих кодов терминала или функций, которые сделают ваш код слишком сложным).

Вместо этого рассмотрите возможность использования " матричный буфер, где каждая «строка» дерева хранится в одной строке в массиве «2D».

Для дерева, подобного вашему, буфер может выглядеть примерно так: 

int buffer[3][4];

Тогда buffer[0][0] будет root дерева, buffer[1][0] будет 2 узлом, buffer[1][1] будет 9 узлом, а buffer[2] будет содержать все конечные узлы.

Затем, чтобы напечатать, вы просто перебираете «буфер» и равномерно распределяете все узлы (необходим эксперимент).

Это требует, чтобы вы знали (или имели функции, которые позволили бы вам учиться) глубину дерево, а также количество узлов листьев. Для чистого двоичного дерева это довольно просто выяснить.

1 голос
/ 28 февраля 2020

Начните с std::vector<node*> frontier = { root_node }

Затем повторите следующее:

  • Печать node->value для каждого элемента в frontier, рядом на одной строке.
  • Снова пройдитесь frontier и соберите все указатели node->left и node->right в новый вектор. Присвойте это frontier.
  • Если любой из дочерних указателей имеет значение NULL, остановитесь.
...