How to display binary search tree in console properly?
I’m trying to display a BST in console. That’s my code (it’s a modified version of code found here: Printing Level Order Binary Search Tree Formatting):
string printLevel(node *root, int level, string gap) < if (!root) < return gap + "-" + gap; >if (level==1) < stringstream out; outvalue; return gap + out.str() + gap; > else if (level>1) < string leftStr = printLevel(root->left, level-1, gap); string rightStr = printLevel(root->right, level-1, gap); return leftStr + " " + rightStr; > else return ""; > void printLevelOrder (node* root, int depth) < for (int i=1; istring levelNodes = printLevel(root, i, gap); cout > If I undestand correctly, the recursion stops when the program makes it to the empty leaf and therefore there are lacking » — » on the lower levels in the result. But how do I know how much of those I should draw on the lower levels? How to make this work?
@MatthieuM. That’s actually bound to the main issue. If the tree was displayed correctly, the 3 would have been on its place. In the means of data structure, it is a right child of the 2 .
3 Answers 3
I instrumented the code to see where it went awry (since running a debugger in a browser. ), you can see it live here. The reproduced function is:
string printLevel(node *root, int level, string gap) < if (root == 0) < cout if (level==1) < stringstream out; outvalue; cout value else if (level>1) < string leftStr = printLevel(root->left, level-1, gap); string rightStr = printLevel(root->right, level-1, gap); cout else return ""; > And here is the bit of interesting output:
.. printLevel - : - .. printLevel - : - .. printLevel - < 3, , >: 3 .. printLevel - < 2, , < 3, , > >: '-', '3' .. printLevel - < 1, , < 2, , < 3, , > > >: '-', '- 3' So, the issue is that you short-circuit whenever root is 0, which is actually an issue: — is not the right output unless level is 1 .
The only difference between root being 0 and root not being 0 is that you cannot read the value out of it (and thus get to replace it by — ); however you only really read that value when level is 1 (beware, you might try to read left or right too), therefore there is no reason to test for root == 0 unless you are in the level == 1 branch.
Let us slightly reorder things then:
string printLevel(node *root, int level, string gap) < if (level==1) < // if (root == 0) < // cout stringstream out; outvalue; cout value else if (level>1) < // string leftStr = printLevel(root ? root->left : 0, level-1, gap); // string rightStr = printLevel(root ? root->right : 0, level-1, gap); cout else return ""; > Note: I «highlighted» the modified lines with «comments».
And now, the tree prints properly.
Источник
Вывод дерева в консоли
Вывод в консоли красивого бинарного дерева
Я пробегаюсь по дереву (вычисляю количество уровней) и строю массив указателей на однонаправленный.
Вывод бинарного дерева на экран в виде «дерева»
основная задача: подсчет количества листьев. проблема: при просмотре хочу выводить бин. дерево, в.
вывод дерева
помогите вывести дерево в отсортированном виде вот код создания дерева #include <stdio.h>.
Вывод дерева на экран
Создаю бинарное дерево, заполняю его случайными числами. Хотелось бы все это дело аккуратно вывести.
1 2 3 4 5 6 7 8 9 10 11 12
void Print(Node *q, long n) { long i; if (q) { Print(q->right, n+5); for (i = 0; i n; i++) printf(" "); printf("%d\n", q->data); Print(q->left, n+5); } }
Спасибо, а не подскажете еще почему моя функция создания дерева использует только первые несколько чисел?
Сообщение от xam max 
Спасибо, а не подскажете еще почему моя функция создания дерева использует только первые несколько чисел?
Потому что неправильно элементы из массива берутся. Используйте указатель на индекс очередного элемента
Добавлено через 8 минут
Вот, немного переделал вашу программу:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
#include #include #include #include using namespace std; struct Node { int key; Node *right,*left; }; typedef Node *KNode; const int n=23; KNode maketree(int mass[],int *from, int n) { KNode tree; if(n==0) return NULL; int nr,nl; tree=new Node; tree->key=mass[*from]; (*from)++; nl=n/2; nr=n-nl-1; tree->left=maketree(mass,from,nl); tree->right=maketree(mass,from,nr); return tree; } void PrintTree (KNode tree, int r) { if(tree!=NULL) { PrintTree(tree->right, r+5); for (int i=0; i r ; i++) printf(" "); printf("%d\n",tree->key); PrintTree(tree->left, r+5); } } int _tmain(int argc, _TCHAR* argv[]) { srand(time(NULL)); int mass[n], i; for(int i=0;in;i++) mass[i]=0; for(int i=0;in;i++) mass[i]=((rand()%9)+1)*10+rand()%10; /*for(int i=0;i for(int j=i+1;j if(mass[i]=mass[j]) mass[j]=((rand()%9)+1)*1000+rand()%100; j=i+1; >*/ printf("Initial sequence\n"); for(int i=0;in;i++) printf("%i ",mass[i]); printf("\n"); KNode Tree; i = 0; Tree=maketree(mass,&i,n); PrintTree(Tree,0); getch(); return 0; } Источник
Вывод бинарного дерева на экран в виде «дерева»
основная задача: подсчет количества листьев.
проблема: при просмотре хочу выводить бин. дерево, в красивом виде, возможно использование псевдографики
интересует алгоритм и идеи
Пы.Сы.: так же интересует любая инфа по теме основного задания.
Запись массива в виде бинарного дерева и вывод его на экран!
Задача: Зарандомить массив с 30 ел. от -100 до 100, создать бинарное дерево использую дан.
«Рекурсивная функция» (Обход бинарного дерева)
Привет всем, встретился с такой рекурсивной ф-ей, которая обходит бинарное дерево и выводит его на.
Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя — 1 указатель на.
Работа с бинарным деревом: добавить элемент, удалить элемент, вывести в виде «дерева»
Создать программу для работы с бинарным деревом, реализующую функции: добавить элемент, удалить.
Могу скинуть функцию распечатывания в консоли дерева. Она только немного будет на 90 градусов в лево перевёрнуто, но наглядно достаточно.
Добавлено через 1 минуту
А подсчёт кол-во листьев, просто обойти все дерево, в глубину или в ширину (как вам больше нравиться), тут лучше в ширину наверное будет, для подсчёта кол-ва.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
// лабаДеревья.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include #include #include #include #include #define FL typedef struct link { int key; link *left; link *right; } node; void GoToXY (short x, short y) { HANDLE StdOut = GetStdHandle(STD_OUTPUT_HANDLE); COORD coord = {x, y}; SetConsoleCursorPosition(StdOut, coord); } node * search (node * tree, int key) { node *buf; if (tree) do { buf=tree; if (tree->key==key) return NULL; if (keytree->key) tree=tree->left; else tree=tree->right; } while (tree); return buf; } int Add (node **tree, int key) { node * buf; #ifdef FL if (! ( buf = (node *) malloc ( sizeof (node) ) ) ) { printf ("\nNo free memory"); return -1; } #else buf = new node; #endif buf->key=key; buf->left=NULL; buf->right=NULL; if (!*tree) { *tree=buf; return 1; } if (search(*tree,key)) { if (keysearch(*tree,key)->key) search(*tree,key)->left=buf; else search (*tree,key)->right=buf; } else return -1; return 0; } /*void iteration (node * root) if (root) printf ("%5d", root->key); iteration (root->left); iteration (root->right); > >*/ void Free(node *&root) { if (root->left) Free(root->left); if (root->right) Free(root->right); #ifdef FL free ( root ); #else delete root; #endif root = NULL; } void print (node * root, short x, short y, short a, char c) { if (root) { if (a>0 && c!='k') { if (c=='l') x-=10; else x+=10; } else if (c!='k') if (c=='l') x-=4; else x+=4; GoToXY (x,y+=2); a--; printf ("%5d", root->key); print (root->left,x,y,a,'l'); print (root->right,x,y,a,'r'); } } void list (node * root, short x, short y, short a, char c) { if (root) { if (a>0 && c!='k') { if (c=='l') x-=10; else x+=10; } else if (c!='k') if (c=='l') x-=4; else x+=4; GoToXY (x,y+=2); a--; if ( !root->left && !root->right ) printf ("%5d", root->key); list (root->left,x,y,a,'l'); list (root->right,x,y,a,'r'); } } void del (node **root, int value) { if (!*root) { printf ("No key\n"); fflush (stdin); getch (); return ; } if (value (*root)->key) del (&(*root)->right,value); else if (value > (*root)->key) del (&(*root)->right,value); else { node *buf=(*root)->left; node *t =(*root)->right; free (*root); *root=t; while (*root) root = &(*root)->left; *root = buf; } } size_t Count ( node *root, bool f = true ) static size_t count; if ( f ) count = 0; if ( root ) { if ( ( root->left && ! root->right ) return count; } int main(int argc, char* argv[]) { node *tree=NULL; int key; char a; system ("cls"); //Add (&tree,3); Add (&tree,5); Add (&tree,1); Add (&tree,0); Add (&tree,7); Add (&tree,7); //print (tree,37,5,2,'k'); printf ("\n"); do { printf ("\n 1-Dobavit`; 2-Delete; 3- Print; 4 - list; 5 - Count; 6 - Del_Tree 0-Vuhod"); fflush (stdin); a=getch(); printf ("\n"); switch (a) { case '1' : while (!(fflush (stdin) ) && ! ( printf ("Enter key " ) && scanf ("%d",&key) ) ); Add (&tree,key); break; case '2' : while (!(fflush (stdin) ) && ! ( printf ("Enter key to delete " ) && scanf ("%d",&key) ) ); del (&tree, key); break; case '3' : printf ("Tree : "); if (!tree) printf ("None"); else //iteration (tree); print (tree,37,5,2,'k'); printf ("\n\n\n\n\n\n"); system ("pause"); break; case '4' : printf ("Tree list : "); if (!tree) printf ("None"); else //iteration (tree); list (tree,37,5,2,'k'); printf ("\n\n\n\n\n\n"); system ("pause"); break; case '5' : printf ("\n Count = %d \n", Count (tree) ); system ("pause"); break; case '6' : Free (tree); break; } system ("cls"); } while (a!='0'); system ("pause"); return 0; }
Источник