Вывод бинарного дерева на консоль
Бинарное дерево – это структура данных, которая состоит из узлов, каждый из которых имеет не более двух потомков. Бинарные деревья широко используются в программировании для организации данных. В данной статье мы рассмотрим, как вывести бинарное дерево на консоль.
Что такое бинарное дерево?
Бинарное дерево – это структура данных, которая состоит из узлов, каждый из которых имеет не более двух потомков. Потомки узла могут быть либо другими узлами бинарного дерева, либо не иметь потомков вообще. Узел, у которого нет потомков, называется листом.
Каждому узлу бинарного дерева соответствует определенное значение, которое может быть любым типом данных. Для примера мы будем использовать бинарное дерево, состоящее из чисел.
Создание бинарного дерева
Для начала создадим бинарное дерево. Мы будем использовать класс Node для описания узлов дерева:
class Node < public: int value; Node* left; Node* right; Node(int value) < this->value = value; this->left = nullptr; this->right = nullptr; > >;
Здесь мы определяем класс Node, который имеет три поля: value, left и right. Поле value хранит значение узла, а поля left и right указывают на левого и правого потомка соответственно. Конструктор класса Node принимает значение value, инициализирует поля left и right значением nullptr.
Далее создадим функцию для добавления узлов в бинарное дерево:
Node* insert(Node* root, int value) < if (root == nullptr) return new Node(value); if (value < root->value) root->left = insert(root->left, value); else if (value > root->value) root->right = insert(root->right, value); return root; >
Эта функция принимает указатель на корневой узел дерева и значение, которое нужно добавить в дерево. Если корневой узел равен nullptr, это означает, что дерево пустое, и мы создаем новый узел с заданным значением. Если значение меньше значения корневого узла, мы добавляем его в левое поддерево, иначе – в правое поддерево.
Теперь мы можем создать бинарное дерево и заполнить его значениями:
В результате выполнения этого кода мы получим бинарное дерево с корневым узлом со значением 10, левым поддеревом со значениями 5 и 7 и правым поддеревом со значениями 15, 13 и 20.
Вывод бинарного дерева на консоль
Чтобы вывести бинарное дерево на консоль, нам нужно обойти все его узлы и вывести их значения. Существует несколько способов обхода бинарного дерева:
— Прямой обход (pre-order traversal) – сначала посещаем корневой узел, затем левое поддерево и правое поддерево.
— Симметричный обход (in-order traversal) – сначала посещаем левое поддерево, затем корневой узел и правое поддерево.
— Обратный обход (post-order traversal) – сначала посещаем левое поддерево, затем правое поддерево и корневой узел.
Для вывода бинарного дерева на консоль мы будем использовать симметричный обход, который выводит узлы в порядке возрастания.
Симметричный обход реализуется с помощью рекурсии. В каждом рекурсивном вызове мы просматриваем узел, его левое поддерево и правое поддерево.
Вот код функции для вывода бинарного дерева на консоль:
void printInOrder(Node* root) < if (root == nullptr) return; printInOrder(root->left); std::cout value right); >
Эта функция принимает указатель на корневой узел дерева и выводит все его узлы на консоль в порядке возрастания. Сначала мы проверяем, что указатель на узел не равен nullptr, что означает, что мы еще не дошли до конца дерева. Затем рекурсивно вызываем функцию printInOrder для левого поддерева, выводим значение корневого узла и рекурсивно вызываем функцию printInOrder для правого поддерева.
Чтобы вывести на консоль бинарное дерево, созданное ранее, мы вызываем функцию printInOrder следующим образом:
В результате мы получим на консоль значения узлов бинарного дерева в порядке возрастания: 5 7 10 13 15 20.
Бинарные деревья – важная структура данных, которая широко используется в программировании. В данной статье мы рассмотрели, как создать и вывести на консоль бинарное дерево при помощи языка программирования C++. Вывод бинарного дерева на консоль может быть реализован разными способами, в данной статье мы использовали симметричный обход, который выводит узлы в порядке возрастания. Знание работы с бинарными деревьями может быть полезным при разработке сложных программных систем, использующих различные структуры данных.
Источник
Как вывести бинарное дерево в красивом виде?
У меня получилось бинарное дерево однобокое.
Выводит все по одной стороне, не понимаю, как переписать функцию печати, дабы дерево выводилось в красивом виде по узлам (прикрепляю картинку +- того, что хотелось бы получить на выводе — без графики, просто красивое
оформление текста на выходе)
#include #include #include #include using namespace std; struct BinTree < int value; BinTree* left; BinTree* right; >; //Функция для создания дерева void newBinTree(int val, BinTree** Tree) < if ((*Tree) == NULL)< (*Tree) = new BinTree; //Выделить память (*Tree)->value = val; (*Tree)->left = (*Tree)->right = NULL; return; > if (val > (*Tree)->value) newBinTree(val, &(*Tree)->right); else newBinTree(val, &(*Tree)->left); > void Print(BinTree** Tree, int l) < int i; if (*Tree != NULL)< Print(&((**Tree).right), l + 1); for (i = 1; i Print(&((**Tree).left), l + 1); > > int NumberOfNodes(BinTree* Tree) < //Получаем количество элементов в дереве if (Tree == NULL) return 0; return NumberOfNodes(Tree->left) + 1 + NumberOfNodes(Tree->right); > void DestroyBTree(BinTree* Tree) < //Удаляем дерево для освобождения памяти if (Tree != NULL) < DestroyBTree(Tree->left); DestroyBTree(Tree->right); delete(Tree); > > void MenuProc() < BinTree* Tree = NULL; int val; int valSum = 0; while (_getch() != 27) < cout > val; valSum += val; newBinTree(val, &Tree); > Print(&Tree, 0); cout "; cout int main()
тогда встает вопрос о размерах дерева: даже относительно небольшое дерево может просто не поместиться в вашей консоли. Но в любом случае отрисовка в консоли данного дерева будет выглядеть примерно так: считаете общее количество элементов в дереве и занимаемый ими размер в одной строке, а дальше идете от корня вниз и принтите ваше ноды начиная с середины строки (размер которой у вас уже должен быть) постепенно расширяясь влево и вправо
1 ответ 1
Только что для вас написал две функции (два варианта) для вывода дерева в консоль, первый вариант (функция dump0()) супер короткий и простой, но выводит немного в другом виде чем вы хотели, второй вариант довольно громоздкий (функция dump1()), но делает ровно то что вы хотели (даже наверное красивее), также сделал функцию dump2() она похожа на dump0() только выводит в порядке «правый, корень, левый», когда dump0() выводила «корень, левый, правый».
Также реализовал две версии — ASCII/UNICODE, в конце ответа вывод консоли вначале ASCII для всех dump()-ов, потом UNICODE для всех. Юникод вариант использует спец символы для рисования рамок/окон/таблиц взятые с этой страницы. У кого СтэкОверфлоу не показывает юникод, то можете посмотреть пример вывода на этой картинке в браузере или на этой картинке в консоле.
Я ваш полный код не использовал, вместо этого скопировал только вашу BinTree структуру. Также у себя в коде не делал очистку ресурсов и памяти у BinTree, конечно в вашем коде вы должны очистку делать. Сами функции dump0/dump1 всё за собой чистят, т.е. для них доработок не нужно никаких.
Пример использования в функции main(), там создание дерева плюс вызов двух видов вывода в консоль.
Промотайте мой ответ в самый конец, там я вывел текст который был выдан в консоль обоими функциями.
Мой код полностью встроенный в ваш можно скачать по ссылке тут.
#include #include #include #include #include #include #include #include #ifdef _WIN32 #include #else #include #endif struct BinTree < int value; BinTree* left; BinTree* right; >; #define LN < std::cout #define DEB(x) < std::cout // https://en.wikipedia.org/wiki/Box_Drawing_(Unicode_block) static std::string ch_hor = "-", ch_ver = "|", ch_ddia = "/", ch_rddia = "\\", ch_udia = "\\", ch_ver_hor = "|-", ch_udia_hor = "\\-", ch_ddia_hor = "/-", ch_ver_spa = "| "; //static std::string ch_hor = "\u2500" /*─*/, ch_ver = "\u2502" /*│*/, ch_ddia = "\u250C" /*┌*/, ch_rddia = "\u2510" /*┐*/, ch_udia = "\u2514" /*└*/, ch_ver_hor = "\u251C\u2500" /*├─*/, ch_udia_hor = "\u2514\u2500" /*└─*/, ch_ddia_hor = "\u250C\u2500" /*┌─*/, ch_ver_spa = "\u2502 " /*│ */; void dump0(BinTree const * node, std::string const & prefix = "", bool root = true, bool last = true) < std::cout value) : "") left && !node->right)) return; std::vector vleft, node->right>; for (size_t i = 0; i < v.size(); ++i) dump0(v[i], prefix + (root ? "" : (last ? " " : ch_ver_spa)), false, i + 1 >= v.size()); > void dump2(BinTree const * node, std::string const & rpref = "", std::string const & cpref = "", std::string const & lpref = "") < if (!node) return; if (node->right) dump2(node->right, rpref + " ", rpref + ch_ddia_hor, rpref + ch_ver_spa); std::cout value) left) dump2(node->left, lpref + ch_ver_spa, lpref + ch_udia_hor, lpref + " "); > void dump4(BinTree const * node, bool high = true, std::vector const & lpref = std::vector(), std::vector const & cpref = std::vector(), std::vector const & rpref = std::vector(), bool root = true, bool left = true, std::shared_ptr> lines = nullptr) < if (!node) return; typedef std::vectorVS; auto VSCat = [](VS const & a, VS const & b)< auto r = a; r.insert(r.end(), b.begin(), b.end()); return r; >; if (root) lines = std::make_shared>(); if (node->left) dump4(node->left, high, VSCat(lpref, high ? VS() : VS()), VSCat(lpref, high ? VS() : VS()), VSCat(lpref, high ? VS() : VS()), false, true, lines); auto sval = std::to_string(node->value); size_t sm = left || sval.empty() ? sval.size() / 2 : ((sval.size() + 1) / 2 - 1); for (size_t i = 0; i < sval.size(); ++i) lines->push_back(VSCat(i < sm ? lpref : i == sm ? cpref : rpref, )); if (node->right) dump4(node->right, high, VSCat(rpref, high ? VS() : VS()), VSCat(rpref, high ? VS() : VS()), VSCat(rpref, high ? VS() : VS()), false, false, lines); if (root) < VS out; for (size_t l = 0;;++l) < bool last = true; std::string line; for (size_t i = 0; i < lines->size(); ++i) if (l < (*lines).at(i).size()) < line += lines->at(i)[l]; last = false; > else line += " "; if (last) break; out.push_back(line); > for (size_t i = 0; i < out.size(); ++i) std::cout > void dump3(BinTree * root, int space = 0) < if (!root) return; enum < COUNT = 2 >; space += COUNT; dump3(root->right, space); for (int i = COUNT; i < space; ++i) std::cout value left, space); > void dump1(BinTree const * node) < #define _MAX(x, y) ((x) >(y) ? (x) : (y)) #define _MIN(x, y) ((x) < (y) ? (x) : (y)) auto RepStr = [](std::string const & s, size_t cnt) < if (ptrdiff_t(cnt) < 0) throw std::runtime_error("RepStr: Bad value " + std::to_string(ptrdiff_t(cnt)) + "!"); std::string r; for (size_t i = 0; i < cnt; ++i) r += s; return r; >; std::function(BinTree const * node, bool)> Rec; Rec = [&RepStr, &Rec](BinTree const * node, bool left) < std::vectorlines; if (!node) return std::make_tuple(lines, size_t(0), size_t(0)); auto sval = std::to_string(node->value); //if (sval.size() % 2 != 1) sval += " "; auto resl = Rec(node->left, true), resr = Rec(node->right, false); auto const & vl = std::get(resl); auto const & vr = std::get(resr); auto cl = std::get(resl), cr = std::get(resr), lss = std::get(resl), rss = std::get(resr); size_t lv = sval.size(); size_t ls = vl.size() > 0 ? lss : size_t(0); size_t rs = vr.size() > 0 ? rss : size_t(0); size_t lis = ls == 0 ? lv / 2 : _MAX(int(lv / 2 + 1 - (ls - cl)), 0); size_t ris = rs == 0 ? (lv + 1) / 2 : _MAX(int((lv + 1) / 2 - cr), (lis > 0 ? 0 : 1)); size_t dashls = (ls == 0 ? 0 : ls - cl - 1 + lis - lv / 2), dashrs = (rs == 0 ? 0 : cr + ris - (lv + 1) / 2); //DEB(node->value); DEB(lv); DEB(ls); DEB(rs); DEB(cl); DEB(cr); DEB(lis); DEB(ris); DEB(dashls); DEB(dashrs); std::cout return std::make_tuple(lines, (left || ls + lis == 0 || lv % 2 == 1) ? ls + lis : ls + lis - 1, ls + lis + ris + rs); >; auto v = std::get(Rec(node, true)); for (size_t i = 0; i < v.size(); ++i) std::cout int main() < #ifdef _WIN32 SetConsoleOutputCP(65001); #else setlocale(LC_ALL, "en_US.UTF-8"); #endif try < auto tree = new BinTree>, new BinTree, 0>, >, >, new BinTree, new BinTree, new BinTree>, >, >; std::cout catch (std::exception const & ex) < std::cout > ====== ASCII ====== ===dump0=== 10 |-5 | |-1 | | |- | | \-2 | \-6 | |- | \-8 | |-7 | \- \-19 |-17 \-21 |-20 \-250 ===dump1=== /--10--\ /-5\ /19-\ 1\ 6-\ 17 /21\ 2 /8 20 250 7 ===dump2=== /-250 /-21 | \-20 /-19 | \-17 10 | /-8 | | \-7 | /-6 \-5 | /-2 \-1 ===dump3=== 250 21 20 19 17 10 8 7 6 5 2 1 ===dump4_high=== /---10--\ | | /-5\ /19--\ | | | | 1\ 6-\ 17 /21-\ | | | | 2 /8 20 250 | 7 ===dump4_low=== /---10--\ /-5\ /19--\ 1\ 6-\ 17 /21-\ 2 /8 20 250 7 ====== UNICODE ====== ===dump0=== 10 ├─5 │ ├─1 │ │ ├─ │ │ └─2 │ └─6 │ ├─ │ └─8 │ ├─7 │ └─ └─19 ├─17 └─21 ├─20 └─250 ===dump1=== ┌──10──┐ ┌─5┐ ┌19─┐ 1┐ 6─┐ 17 ┌21┐ 2 ┌8 20 250 7 ===dump2=== ┌─250 ┌─21 │ └─20 ┌─19 │ └─17 10 │ ┌─8 │ │ └─7 │ ┌─6 └─5 │ ┌─2 └─1 ===dump4_high=== ┌───10──┐ │ │ ┌─5┐ ┌19──┐ │ │ │ │ 1┐ 6─┐ 17 ┌21─┐ │ │ │ │ 2 ┌8 20 250 │ 7 ===dump4_low=== ┌───10──┐ ┌─5┐ ┌19──┐ 1┐ 6─┐ 17 ┌21─┐ 2 ┌8 20 250 7 Источник