Печать BST сбоку сверху донизу

У меня есть вопрос, связанный с печатью BST. Я мог бы печатать дерево сбоку, используя другой алгоритм печати дерева. Тем не менее, я всегда печатаю дерево слева направо. Так есть ли способ распечатать дерево вверх дном? Я видел некоторое представление об использовании XY, но я не хочу делать это в консоли, так есть ли какой-либо другой метод для достижения того же?Печать BST сбоку сверху донизу

Редактировать: Например, у меня есть входы как L, M, R, T, S, G, Y, S, D, Е, С, А. С помощью симметричного обхода, я получил этот вход

То, что я хочу, это то же самое, что вращать эту 90 градусов вправо, а L должен быть сверху, а затем остальные.

Редактировать 2: Вот код, использующий Order Level для печати дерева, однако я не уверен, как отобразить формат, который я хотел.

queue<TreeNode*> q; 

while(node != NULL) 
{ 
    cout << node->data << " " << endl; 
    if (node->left) 
     q.push(node->left); 
    if(node->right) 
     q.push(node->right); 
    if(!q.empty()) 
    { 
     node = q.front(); 
     q.pop(); 
    } 
    else 
     node = NULL; 
}

источник

2012-03-25 Spincel

ли реализация дерева есть ссылка на их родительские узлы? Если это так, я думаю, что это должно быть возможно. Если нет, вы можете запустить обычную печать и сохранить эти значения в массиве, а затем повернуть назад (это было бы довольно неэффективно). – twain249

Что вы подразумеваете под «перевернутым»? –

Да, есть указатели слева и справа. – Spincel

Возможно, вы имели в виду Breadth-First Search?

источник

2012-03-25 23:25:30 josephthomas

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

Как вы это сделаете вручную? Это реальный вопрос; код C++ просто записывает все этапы. Мой подход состоял бы в том, чтобы напечатать верхний узел L в центре, поэтому с 40 пробелами перед ним. Узлы второго уровня, я бы напечатал с 20 (G), а затем 40 (M) пространства перед. На третьем уровне я напечатал 10 пробелов, затем C, затем 20 пробелов и т. Д.

I.e. на глубине D у меня есть 2 ^D элементы, которые мне нужно распечатать, поэтому каждый из них получает ширину linewidth>>D.

источник

2012-03-26 09:18:50 MSalters

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

первой функции - уровень принты на уровне (корневые лв -> листов лв)
второй функция - расстояние от начала новой строки
третьей функции - печать узлов и вычисляет расстояние между два отпечатка;

void Tree::TREEPRINT() 
{ 
    int i = 0; 
    while (i <= treeHeight(getroot())){ 
     printlv(i); 
     i++; 
     cout << endl; 
    } 
} 

void Tree::printlv(int n){ 
    Node* temp = getroot(); 
    int val = pow(2, treeHeight(root) -n+2); 
    cout << setw(val) << ""; 
    prinlv(temp, n, val); 
} 

void Tree::dispLV(Node*p, int lv, int d) 
{ 
    int disp = 2 * d; 
    if (lv == 0){ 
     if (p == NULL){ 

      cout << " x "; 
      cout << setw(disp -3) << ""; 
      return; 
     } 
     else{ 
      int result = ((p->key <= 1) ? 1 : log10(p->key) + 1); 
      cout << " " << p->key << " "; 
      cout << setw(disp - result-2) << ""; 
     } 
    } 
    else 
    { 
     if (p == NULL&& lv >= 1){ 
      dispLV(NULL, lv - 1, d); 
      dispLV(NULL, lv - 1, d); 
     } 
     else{ 
      dispLV(p->left, lv - 1, d); 
      dispLV(p->right, lv - 1, d); 
     } 
    } 
}

Вход:

50-28-19-30-29-17-42-200-160-170-180-240-44-26-27

Выход: https://i.stack.imgur.com/TtPXY.png

источник

2017-07-31 22:30:31

Печать BST сбоку сверху донизу

ответ

Смежные вопросы