Вывод элементов бинарного дерева

Красивый вывод бинарного дерева C#

Написал структуру бинарного дерева, в которое можно добавлять элементы. Подскажи как можно сделать , чтобы можно было его красиво выводить в консоль в виде дерева именно , а не в строку. Искал в интернете примеры , но по шарпу мало чего нашел , в основном не то

using System.Collections; using System.Collections.Generic; namespace BinaryTree < public class Tree < private int _size = 0; private class TreeNode //Ветка < public char Value; public TreeNode Parent, Left, Right; public TreeNode(char value, TreeNode parent = null) < Left = null; Right = null; Parent = parent; Value = value; >> private TreeNode Root; //Корень public Tree() < Root = null; >public void Add(char value) < if (Root == null) < Root = new TreeNode(value); ++_size; >else < TreeNode iterator = Root; while (true) < if (value >iterator.Value) < if (iterator.Right != null) iterator = iterator.Right; else < iterator.Right = new TreeNode(value, iterator); ++_size; break; >> else < if (iterator.Left != null) iterator = iterator.Left; else < ++_size; iterator.Left = new TreeNode(value, iterator); break; >> > > > > > 

чтобы можно было его красиво выводить у каждого своё понятие о красоте. Будьте более конкретны и покажите, как вы сами пытались решить вашу проблему.

@tym32167, нужен просто вывод с выделением веток. Мои попытки не были успешными , поэтому сложно показать что-то конкретное

Реализовать как у вас на картинке сложнее — придется обходить дерево дважды, чтобы вычислить первоначальный отступ.

А как выводить, если в этом случае: pastebin.com/uqkPWK3X — если глубина дерева увеличится ещё на один уровень? Делать линии длиннее? Какие?

2 ответа 2

Готовый вариант не дам, но покажу как это сделано а) в графике б) для полных (complete) деревьев, посмотрите подход и сделаете по аналогии.

Во-первых, нужно помнить, что бинарное дерево можно представить не столько в динамической форме, но и в форме массива. Для примера покажу из массива, но для неполного дерева можете написать какие угодно варианты — вполне возможно, что формулы окажутся проще.

Во-вторых, вам нужно хорошо знать зависимости между различными параметрами в бинарном дереве. Что-то я почерпнул отсюда: complete binary tree, что-то сам на листочке выписывал. Вот примерно это мне понадобилось:

Ну и поехали (не всё, ключевые моменты):

Просто сгенерируем массив, это и будет наше дерево:

public int[] GenerateFullBinaryTreeRandom(int height) < var t = (2 rand.Next(0,42)).ToArray(); > 

И обойдём все узлы дерева, по пути отрисовывая их:

public static class TreeOrderHelper < // ширина одной "клетки" private const int box = 50; public static void Display(this TreeNode root) < var canvas = new Canvas().Dump(); if (root == null) return; var arr = root.ToArray(); Display(arr, canvas); >private static void Display(int[] arr, Canvas canvas) < var h = TreeNodeExtension.LevesTotal(arr.Length); for (int i = 0; i < arr.Length; i++) < DrawNode(arr[i].ToString(), canvas, GetX(h, i), GetY(i)); if (h + 1 - TreeNodeExtension.CurrentLevel(i) == 1) continue; var xN = GetX(h, i); var yN = GetY(i); var xL = GetX(h, 2 * i + 1); var yL = GetY(2 * i + 1); var xR = GetX(h, 2 * i + 2); var yR = GetY(2 * i + 2); canvas.Children.Add(new Line < X1 = xN, Y1 = yN, X2 = xL, Y2 = yL, Stroke = Brushes.Gray, StrokeThickness = 0.5d >); canvas.Children.Add(new Line < X1 = xN, Y1 = yN, X2 = xR, Y2 = yR, Stroke = Brushes.Gray, StrokeThickness = 0.5d >); > > private static int GetX(int h, int i) < var l = TreeNodeExtension.CurrentLevel(i); var w1 = (int)Math.Pow(2, l - 1); var o = i - w1 + 1; var d = h + 1 - l; var f = (int)Math.Pow(2, d - 1) - 1; var s = (int)Math.Pow(2, d); var x = 20 + f * box + s * o * box; return x; >private static int GetY(int i) < var y = box * TreeNodeExtension.CurrentLevel(i); return y; >private static void DrawNode(string val, Canvas canvas, int x, int y) < const double PT_DM = 10; var e = new Ellipse < Width = PT_DM, Height = PT_DM, Margin = new Thickness(x - PT_DM / 2, y, 0, 0), Stroke = Brushes.Transparent, Fill = Brushes.SteelBlue, StrokeThickness = 0.5d, >; var t = new TextBlock() < Text = val, Margin = new Thickness(x + PT_DM / 2, y + PT_DM / 2, 0, 0), Foreground = Brushes.Gray, >; canvas.Children.Add(e); canvas.Children.Add(t); > > 

И что-то ещё из этого extension’а понадобится:

public static class TreeNodeExtension < public static TreeNode FromArray(this int[] arr) < if (!ValidateLength(arr.Length)) throw new ArgumentOutOfRangeException(nameof(arr.Length)); return CreateTree(arr); >public static int[] ToArray(this TreeNode root) < var result = new List(); var queue = new Queue(); if (root != null) queue.Enqueue(root); while (queue.Count != 0) < var levelSize = queue.Count; for (int i = 0; i < levelSize; i++) < var dequeued = queue.Dequeue(); result.Add(dequeued.val); if (dequeued.left != null) queue.Enqueue(dequeued.left); if (dequeued.right != null) queue.Enqueue(dequeued.right); >> return result.ToArray(); > public static int LevesTotal(int length) < var total = 0; var i = 0; while(i < 32) < total = (1 if(length != total) throw new Exception(); return i; > public static int CurrentLevel(int length) < var i = 1; var sum = 0; while (i < 32) < sum += 1 return i; > > 

На выходе отрисует примерно такую картинку:

В текстовом виде у вас будут примерно такие же шаги по построению, но только будете рисовать виртуальные клетки и делать паддинги:

Там есть пара подводных камней, поэтому я пока не доделал этот скрипт до конца. Сделаете — опубликуйте соседним ответом и поставьте галку.

PS Я свой код особо не оптимизировал, в своё время потратил пару недель только на то, чтобы написать рабочий прототип, поэтому если у кого-то будут идеи что и как улучшить — пишите, интересно. Топикстартер прав: по этой теме в интернете особо информации нет, да и в книгах тоже не особо.

Как уже было сказано, решать задачу в текстовом режиме — не лучшая идея, поскольку наши углы наклона стрелок ограничены по сути ровно одним значением. Поэтому вот вам решение на WPF. Раз уж мы пользуемся WPF, то надо использовать существующий в поставке layout manager.

Поскольку дерево — рекурсивная структура данных, мы создадим рекурсивный UserControl . (Возможно, подход с кастомизацией TreeView был бы проще.)

Кажется разумным определить такую структуру данных:

class BinaryTree  < public T Value < get; set; >public BinaryTree Left < get; set; >public BinaryTree Right < get; set; >> 

Но работать с неизвестным типом на уровне представления будет неудобно, поэтому добавим ещё и нетипизированный интерфейс:

interface IBinaryTree < public object Value < get; >public IBinaryTree Left < get; >public IBinaryTree Right < get; >> class BinaryTree : IBinaryTree < public T Value < get; set; >public BinaryTree Left < get; set; >public BinaryTree Right < get; set; >object IBinaryTree.Value => Value; IBinaryTree IBinaryTree.Left => Left; IBinaryTree IBinaryTree.Right => Right; > 

Если вы захотите реализовать INotifyPropertyChanged , чтобы WPF на лету подхватывал изменения, почему бы и нет.

Для начала, положим вот такой XAML:

          "/> " Grid.Row="1" Grid.Column="0" /> " Grid.Row="1" Grid.Column="2" />  

Такая штука не сработает, и немедленно приведёт к переполнению стека, ведь дерево контролов получается бесконечным. Даже установка триггера, который отключает Visibility при нулевом DataContext , не спасает. Значит, элементы нужно генерировать динамически. Для этого иcпользуется либо связка ItemsPanel / ItemsHost , либо code-behind. Давайте пойдём через code-behind, это, кажется, будет проще.

" Grid.Row="1" Grid.Column="0" /> " Grid.Row="1" Grid.Column="2" /> 

" Grid.Row="1" Grid.Column="0" /> " Grid.Row="1" Grid.Column="2" /> 

public partial class BinaryTreePresenter : UserControl < public BinaryTreePresenter() < InitializeComponent(); LeftHost.DataContextChanged += OnDataContextChanged; RightHost.DataContextChanged += OnDataContextChanged; >void OnDataContextChanged(object sender, DependencyPropertyChangedEventArgs e) < var host = (Decorator)sender; if (host.DataContext is IBinaryTree) host.Child ??= new BinaryTreePresenter(); else host.Child = null; >> 

Вроде бы всё хорошо, но не хватает стрелок. А также вертикального пространства, которое будут занимать стрелки.

Для начала, как сделать стрелки? Я не стал изобретать велосипед, а украл одолжил готовое решение вот тут.

В XAML добавим ещё один «этаж», в котором будет располагаться стрелка.

             "/> " Grid.Row="2" Grid.Column="0" /> " Grid.Row="2" Grid.Column="2" />  

Затем, нам нужно задать элемент, от низа которого будет тянуться стрелка, то есть, родительский элемент. Но это должен не весь родительский BinaryTreePresenter , т. к. он охватывает наш элемент тоже. Нам нужен его ValueHost (для этого мы и дали ему имя, чтобы сослаться из code-behind).

В code-behind кладём поле FrameworkElement parent; , и присваиваем его, когда создаём внутренний элемент. Мы хотим соединить стрелкой середину верхнего узла с серединой нашего, для этого нам надо знать, когда положение или размер любого из этих элементов поменяется. (Можно сделать это один раз в начале, но тогда при изменении содержания узлов или добавлении/убирании веток стрелки не будут обновляться.)

Для этого я достал из старого проекта вот такой вспомогательный класс:

public class LayoutWatcher : IDisposable < public LayoutWatcher(UIElement target) < this.target = target; target.LayoutUpdated += OnLayoutUpdate; oldRenderSize = target.RenderSize; oldRenderPosition = GetRenderPosition(); >UIElement target; Size oldRenderSize; Point oldRenderPosition; void OnLayoutUpdate(object sender, EventArgs e) < var newRenderSize = target.RenderSize; var newRenderPosition = GetRenderPosition(); var needUpdate = newRenderSize != oldRenderSize || newRenderPosition != oldRenderPosition; oldRenderSize = newRenderSize; oldRenderPosition = newRenderPosition; if (needUpdate) FireChanged(); >Point GetRenderPosition() => target.TranslatePoint(new Point(), null); void FireChanged() => Changed?.Invoke(target, new EventArgs()); public event EventHandler Changed; public void Dispose() < target.LayoutUpdated -= OnLayoutUpdate; >> 

Добавляем обработчик обытия Loaded , в котором мы будем устанавливать слежку за позицией и размерами обеих узлов. Симметрично, добавляем обработчик события Unloaded , в котором будем отписываться от изменений (чтобы не було утечек памяти). Получаем в итоге вот что:

public partial class BinaryTreePresenter : UserControl < public BinaryTreePresenter() < InitializeComponent(); LeftHost.DataContextChanged += OnDataContextChanged; RightHost.DataContextChanged += OnDataContextChanged; Loaded += OnLoaded; Unloaded += OnUnloaded; >void OnLoaded(object sender, RoutedEventArgs e) < if (parent is null) return; ArrowHost.Visibility = Visibility.Visible; selfWatcher = new LayoutWatcher(this); parentWatcher = new LayoutWatcher(this); selfWatcher.Changed += UpdateArrow; parentWatcher.Changed += UpdateArrow; UpdateArrow(null, null); >void UpdateArrow(object sender, EventArgs e) < var start = parent.TranslatePoint(new Point(parent.ActualWidth / 2, parent.ActualHeight), ArrowHost); Arrow.X1 = start.X; Arrow.Y1 = 0; Arrow.X2 = ActualWidth / 2; Arrow.Y2 = ArrowHost.ActualHeight - 2; >void OnUnloaded(object sender, RoutedEventArgs e) < if (selfWatcher is not null) < selfWatcher.Changed -= UpdateArrow; selfWatcher.Dispose(); >if (parentWatcher is not null) < parentWatcher.Changed -= UpdateArrow; parentWatcher.Dispose(); >> FrameworkElement parent; LayoutWatcher selfWatcher, parentWatcher; void OnDataContextChanged(object sender, DependencyPropertyChangedEventArgs e) < var host = (Decorator)sender; if (host.DataContext is IBinaryTree) host.Child ??= new BinaryTreePresenter() < parent = ValueHost >; else host.Child = null; > > 

Отдельных пояснений заслуживает функция UpdateArrow . В ней мы вычисляем при помощи TranslatePoint позицию нижней точки родительского узла относительно ArrowHost . Остальные координаты стрелки рассчитываются очевидным образом.

Источник

C How to «draw» a Binary Tree to the console [closed]

What algorithms can be used to draw a binary tree in the console? The tree is implemented in C. For example, a BST with numbers: 2 3 4 5 8 would be shown in the console as:

Here You have open source library to do what You want: github.com/YoussefRaafatNasry/bst-ascii-visualization

10 Answers 10

From @AnyOneElse Pastbin below:

. . Code originally from /http://www.openasthra.com/c-tidbits/printing-binary-trees-in-ascii/ . Just saved it, cause the website is down. . Printing Binary Trees in Ascii Here we are not going to discuss what binary trees are (please refer this, if you are looking for binary search trees), or their operations but printing them in ascii. The below routine prints tree in ascii for a given Tree representation which contains list of nodes, and node structure is this struct Tree < Tree * left, * right; int element; >; This pic illustrates what the below routine does on canvas.. ascii tree Here is the printing routine.. b5855d39a6b8a2735ddcaa04a404c125001 Auxiliary routines.. //This function prints the given level of the given tree, assuming //that the node has the given x cordinate. void print_level(asciinode *node, int x, int level) < int i, isleft; if (node == NULL) return; isleft = (node->parent_dir == -1); if (level == 0) < for (i=0; i<(x-print_next-((node->lablen-isleft)/2)); i++) < printf(" "); >print_next += i; printf("%s", node->label); print_next += node->lablen; > else if (node->edge_length >= level) < if (node->left != NULL) < for (i=0; iprint_next += i; printf("/"); print_next++; > if (node->right != NULL) < for (i=0; iprint_next += i; printf("\\"); print_next++; > > else < print_level(node->left, x-node->edge_length-1, level-node->edge_length-1); print_level(node->right, x+node->edge_length+1, level-node->edge_length-1); > > //This function fills in the edge_length and //height fields of the specified tree void compute_edge_lengths(asciinode *node) < int h, hmin, i, delta; if (node == NULL) return; compute_edge_lengths(node->left); compute_edge_lengths(node->right); /* first fill in the edge_length of node */ if (node->right == NULL && node->left == NULL) < node->edge_length = 0; > else < if (node->left != NULL) < for (i=0; ileft->height && i < MAX_HEIGHT; i++) < rprofile[i] = -INFINITY; >compute_rprofile(node->left, 0, 0); hmin = node->left->height; > else < hmin = 0; >if (node->right != NULL) < for (i=0; iright->height && i < MAX_HEIGHT; i++) < lprofile[i] = INFINITY; >compute_lprofile(node->right, 0, 0); hmin = MIN(node->right->height, hmin); > else < hmin = 0; >delta = 4; for (i=0; i //If the node has two children of height 1, then we allow the //two leaves to be within 1, instead of 2 if (((node->left != NULL && node->left->height == 1) || (node->right != NULL && node->right->height == 1))&&delta>4) < delta--; >node->edge_length = ((delta+1)/2) - 1; > //now fill in the height of node h = 1; if (node->left != NULL) < h = MAX(node->left->height + node->edge_length + 1, h); > if (node->right != NULL) < h = MAX(node->right->height + node->edge_length + 1, h); > node->height = h; > asciinode * build_ascii_tree_recursive(Tree * t) < asciinode * node; if (t == NULL) return NULL; node = malloc(sizeof(asciinode)); node->left = build_ascii_tree_recursive(t->left); node->right = build_ascii_tree_recursive(t->right); if (node->left != NULL) < node->left->parent_dir = -1; > if (node->right != NULL) < node->right->parent_dir = 1; > sprintf(node->label, "%d", t->element); node->lablen = strlen(node->label); return node; > //Copy the tree into the ascii node structre asciinode * build_ascii_tree(Tree * t) < asciinode *node; if (t == NULL) return NULL; node = build_ascii_tree_recursive(t); node->parent_dir = 0; return node; > //Free all the nodes of the given tree void free_ascii_tree(asciinode *node) < if (node == NULL) return; free_ascii_tree(node->left); free_ascii_tree(node->right); free(node); > //The following function fills in the lprofile array for the given tree. //It assumes that the center of the label of the root of this tree //is located at a position (x,y). It assumes that the edge_length //fields have been computed for this tree. void compute_lprofile(asciinode *node, int x, int y) < int i, isleft; if (node == NULL) return; isleft = (node->parent_dir == -1); lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2)); if (node->left != NULL) < for (i=1; i edge_length && y+i < MAX_HEIGHT; i++) < lprofile[y+i] = MIN(lprofile[y+i], x-i); >> compute_lprofile(node->left, x-node->edge_length-1, y+node->edge_length+1); compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1); > void compute_rprofile(asciinode *node, int x, int y) < int i, notleft; if (node == NULL) return; notleft = (node->parent_dir != -1); rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2)); if (node->right != NULL) < for (i=1; i edge_length && y+i < MAX_HEIGHT; i++) < rprofile[y+i] = MAX(rprofile[y+i], x+i); >> compute_rprofile(node->left, x-node->edge_length-1, y+node->edge_length+1); compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1); > Here is the asciii tree structure… struct asciinode_struct < asciinode * left, * right; //length of the edge from this node to its children int edge_length; int height; int lablen; //-1=I am left, 0=I am root, 1=right int parent_dir; //max supported unit32 in dec, 10 digits max char label[11]; >; 

 2 / \ / \ / \ 1 3 / \ / \ 0 7 9 1 / / \ / \ 2 1 0 8 8 / 7 

Unfortunately it seems so. Couldn’t find it Google Cache or at Internet Archive Wayback machine. This could be it, I haven’t tried to run it yet: datastructuresblog.wordpress.com/2007/12/21/…

The text appears to have become corrupted, and the code link is broken. If anybody can find the code, please help! A link to pastebin might not be out of line.

Источник