Бинарное дерево си шарп

Binary Search Tree in C# Implementation

an infinite loop is caused. I don’t understand what is causing this.Also i would like to know if there is a better way of implementing a BST in C#.

Vote to close: Asking strangers to spot errors in your code by inspection is not productive. You should identify (or at least isolate) the problem by using a debugger or print statements, and then come back with a more specific question (once you’ve narrowed it down to a 10-line test-case).

7 Answers 7

I’m not sure why you need this loop, but answering your question:

this code checks if temp is not null , but it will never become null, cause inside the loop you act only on the leafs of the temp. That’s why you have an infinit loop.

You don’t need a while loop nor a temp variable, let recursion do the work for you:

public void displayTree(Node root)

temp is set to root at the beginning, and after that its value never changes

what about rewriting your function as

public void displayTree(Node root)

It does change when from inside the loop, the function displayTree() is called effectively replacing the value of root as temp.left or temp.right .

 public void displayTree(Node root) < Node temp; temp = root; if (temp != null) < displayTree(temp.left); Console.WriteLine(temp.data + " "); displayTree(temp.right); >> 

I was just thinking that you as well also could use recursion for the add function. It could look something like this

 private void Add(BinaryTree node, ref BinaryTree rootNode) < if (rootNode == null) < rootNode = node; >if (node.value > rootNode.value) < Add(node, ref rootNode.right); >if (node.value < rootNode.value) < Add(node, ref rootNode.left); >> 

See https://msdn.microsoft.com/en-us/library/ms379572%28v=vs.80%29.aspx. See the example code in the section «Traversing the Nodes of a BST»

Also. don’t forget to check out SortedDictionary, etc. They may have the BST that you need all ready to go! https://msdn.microsoft.com/en-us/library/f7fta44c.aspx

Complete Binary Search Tree . With Code to check whether Tree is balanced or not

using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace BinarySearchTree < public class Node < public Node(int iData) < data = iData; leftNode = null; rightNode= null; >public int data public Node leftNode public Node rightNode >; public class Program < public static Node root = null; public static void Main(string[] args) < //Your code goes here Console.WriteLine("Hello, world!"); root = new Node(20); InsertNode(root, new Node(10)); InsertNode(root, new Node(15)); InsertNode(root, new Node(13)); InsertNode(root, new Node(11)); InsertNode(root, new Node(12)); InsertNode(root, new Node(25)); InsertNode(root, new Node(22)); InsertNode(root, new Node(23)); InsertNode(root, new Node(27)); InsertNode(root, new Node(26)); if(CheckIfTreeIsBalanced(root)) < Console.WriteLine("Tree is Balanced!"); >else < Console.WriteLine("Tree is Not Balanced!"); >PrintTree(root); > public static void PrintTree(Node root) < if(root == null) return; Node temp = root; PrintTree(temp.leftNode); System.Console.Write(temp.data + " "); PrintTree(temp.rightNode); >public static bool CheckIfTreeIsBalanced(Node root) < if(root != null) < if(root.leftNode != null && root.rightNode!= null) < if(root.leftNode.data < root.data && root.rightNode.data >root.data) < return CheckIfTreeIsBalanced(root.leftNode)&&CheckIfTreeIsBalanced(root.rightNode); >else < return false; >> else if(root.leftNode != null) < if(root.leftNode.data < root.data) < return CheckIfTreeIsBalanced(root.leftNode); >else < return false; >> else if(root.rightNode != null) < if(root.rightNode.data >root.data) < return CheckIfTreeIsBalanced(root.rightNode); >else < return false; >> > return true; > public static void InsertNode(Node root, Node newNode ) < Node temp; temp = root; if (newNode.data < temp.data) < if (temp.leftNode == null) < temp.leftNode = newNode; >else < temp = temp.leftNode; InsertNode(temp,newNode); >> else if (newNode.data > temp.data) < if (temp.rightNode == null) < temp.rightNode = newNode; >else < temp = temp.rightNode; InsertNode(temp,newNode); >> > > > 

Hello, world! Tree is Balanced! 10 11 12 13 15 20 22 23 25 26 27 

Related

Hot Network Questions

Subscribe to RSS

To subscribe to this RSS feed, copy and paste this URL into your RSS reader.

Site design / logo © 2023 Stack Exchange Inc; user contributions licensed under CC BY-SA . rev 2023.8.15.43579

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.

Источник

H C# и немного алгоритмики: binary trees (реализация, примеры) в черновиках Из песочницы

Всем доброго дня! Давайте немного вспомним азы программирования на C# и повторим, что такое бинарные деревья (binary trees), чем они отличаются от остальных деревьев, что же такое «обход» и каким он бывает.

Данная статья пригодится студентам, начинающим программистам, а также «профи» в качестве справочного материала. Приведены примеры, фрагменты алгоритмов и полный проект на C#. Всех заинтересовавшихся прошу под кат!

Для начала повторим азы. Дерево – связный граф без циклов. Корень – самая верхняя вершина дерева. Лист – вершина, не имеющая потомков. Обход дерева – систематический просмотр всех вершин, при котором каждая вершина встречается один раз.

В рассматриваемых алгоритмах используется бинарное дерево – то есть дерево, в котором каждая вершина имеет два потомка (правые и левые поддеревья – left и right). Добавление реализуется по следующей схеме: при добавлении каждой новой вершины, если значение меньше корня, то оно записывается в левое поддерево, в противном случае – в правое (древесная сортировка).

Реализуем же все перечисленные алгоритмы на языке C#!

Тех, кто хочет немного обновить в памяти данный материал, либо еще только учится программировать базовые алгоритмы, без которых не обойдется ни один программист, прошу под кат!) Все фрагменты кода подробно прокомментированы, а проект на языке C# (VS2012) опубликован на GitHub.

Опишем класс Tree на языке C#:

 public class Tree < // подкласс "элемент дерева" public class TreeNode < public int Value; // численное значение public int Count = 0; // сколько раз было добавлено данное численное значение public TreeNode Left; // левое поддерево public TreeNode Right; // правое поддерево >public TreeNode Node; // экземпляр класса "элемент дерева" > 

 // добавление значения в дерево (рекурсивно) private void AddRecursion(ref TreeNode node, int val) // печать дерева (рекурсивно) private void PrintRecursion(TreeNode node, int spaces, ref string s) // обход дерева в ширину (итерационно, используется очередь) private void Across(TreeNode node, ref string s, bool detailed) // прямой обход (CLR - center, left, right) private void CLR(TreeNode node, ref string s, bool detailed) // обратный обход (LCR - left, center, right) private void LCR(TreeNode node, ref string s, bool detailed) // концевой обход (RCL - left, right, center) private void RCL(TreeNode node, ref string s, bool detailed) 

Обход в глубину

• Прямой обход (CLR – center, left, right). Сначала берется значение корня, затем обходится левое поддерево, затем правое;
• Концевой обход (RCL – right, center, left). Сначала обходится правое поддерево, затем берется значение корня, затем левое;
• Обратный обход (LCR – left, center, right). Сначала обходится левое поддерево, затем берется значение корня, затем правое поддерево.

// прямой обход (CLR - center, left, right) private void CLR(TreeNode node, ref string s, bool detailed) < /* Аргументы метода: 1. TreeNode node - текущий "элемент дерева" (ref передача по ссылке) 2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке) */ if (node != null) < if (detailed) s += " получили значение " + node.Value.ToString() + Environment.NewLine; else s += node.Value.ToString() + " "; // запомнить текущее значение if (detailed) s += " обходим левое поддерево" + Environment.NewLine; CLR(node.Left, ref s, detailed); // обойти левое поддерево if (detailed) s += " обходим правое поддерево" + Environment.NewLine; CLR(node.Right, ref s, detailed); // обойти правое поддерево >else if (detailed) s += " значение отсутствует - null" + Environment.NewLine; > 

// обратный обход (LCR - left, center, right) private void LCR(TreeNode node, ref string s, bool detailed) < /* Аргументы метода: 1. TreeNode node - текущий "элемент дерева" (ref - передача по ссылке) 2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке) */ if (node != null) < if (detailed) s += " обходим левое поддерево" + Environment.NewLine; LCR(node.Left, ref s, detailed); // обойти левое поддерево if (detailed) s += " получили значение " + node.Value.ToString() + Environment.NewLine; else s += node.Value.ToString() + " "; // запомнить текущее значение if (detailed) s += " обходим правое поддерево" + Environment.NewLine; LCR(node.Right, ref s, detailed); // обойти правое поддерево >else if (detailed) s += " значение отсутствует - null" + Environment.NewLine; > 

// концевой обход (RCL -right, center, left) private void RCL(TreeNode node, ref string s, bool detailed) < /* Аргументы метода: 1. TreeNode node - текущий "элемент дерева" (ref передача по ссылке) 2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке) */ if (node != null) < if (detailed) s += " обходим правое поддерево" + Environment.NewLine; RCL(node.Right, ref s, detailed); // обойти правое поддерево if (detailed) s += " получили значение " + node.Value.ToString() + Environment.NewLine; else s += node.Value.ToString() + " "; // запомнить текущее значение if (detailed) s += " обходим левое поддерево" + Environment.NewLine; RCL(node.Left, ref s, detailed); // обойти левое поддерево >else if (detailed) s += " значение отсутствует - null" + Environment.NewLine; >

Обход в ширину

Поддеревья посещаются уровень за уровнем, каждый уровень обходится слева направо. Сложность алгоритма O(V+E), где V – множество вершин, а E-множество дуг.

// обход дерева в ширину (итерационно, используется очередь) private void Across(TreeNode node, ref string s, bool detailed) < /* Аргументы метода: 1. TreeNode node - текущий "элемент дерева" (ref передача по ссылке) 2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке) */ var queue = new Queue(); // создать новую очередь if (detailed) s += " заносим в очередь значение " + node.Value.ToString() + Environment.NewLine; queue.Enqueue(node); // поместить в очередь первый уровень while (queue.Count!=0) // пока очередь не пуста < //если у текущей ветви есть листья, их тоже добавить в очередь if (queue.Peek().Left != null) < if (detailed) s += " заносим в очередь значение " + queue.Peek().Left.Value.ToString() + " из левого поддерева" + Environment.NewLine; queue.Enqueue(queue.Peek().Left); >if (queue.Peek().Right != null) < if (detailed) s += " заносим в очередь значение " + queue.Peek().Right.Value.ToString() + " из правого поддерева" + Environment.NewLine; queue.Enqueue(queue.Peek().Right); >//извлечь из очереди информационное поле последнего элемента if (detailed) s += " извлекаем значение из очереди: " + queue.Peek().Value.ToString() + Environment.NewLine; else s += queue.Peek().Value.ToString() + " "; // убрать последний элемент очереди queue.Dequeue(); > >? 

С использованием данных методов я по-быстрому написал такую вот небольшую программку:

Разберем несколько примеров

Пример 1

Пример: дерево с большим числом поддеревьев, «правых» и «левых».
В глубину CLR: 5 4 3 1 9 8 6 7 15 10
В глубину LCR: 1 3 4 5 6 7 8 9 10 15
В глубину RCL: 15 10 9 8 7 6 5 4 3 1
В ширину: 5 4 9 3 8 15 1 6 10 7

Пример2

Пример: только отрицательные значения в дереве.
В глубину CLR: -2 -4 -15 -5 -1
В глубину LCR: -15 -5 -4 -2 -1
В глубину RCL: -1 -2 -4 -5 -15
В ширину: -2 -4 -1 -15 -5

Пример 3

Пример: отрицательные и положительные значения в дереве
В глубину CLR: 5 4 3 -30 0 1 2 15 8 30
В глубину LCR: -30 0 1 2 3 4 5 8 15 30
В глубину RCL: 30 15 8 5 4 3 2 1 0 -30
В ширину: 5 4 15 3 8 30 -30 0 1 2

Пример 4

Пример: только правые поддеревья
В глубину CLR: 4 5 6 7 8
В глубину LCR: 4 5 6 7 8
В глубину RCL: 8 7 6 5 4
В ширину: 4 5 6 7 8

Пример 5

Пример: только левые поддеревья
В глубину CLR: 10 9 8 7 6
В глубину LCR: 6 7 8 9 10
В глубину RCL: 10 9 8 7 6
В ширину: 10 9 8 7 6

Пример 6

Пример: наиболее емкая наглядность обходов
В глубину CLR: 10 9 11
В глубину LCR: 9 10 11
В глубину RCL: 11 10 9
В ширину: 10 9 11

Исходники проекта

Полные исходники программы для работы с бинарными деревьями выкладываю на GitHub. Можете свободно пользоваться ими для своих проектов или для более локальных задач, к примеру, выполнения лабораторных работ в университете. Присутствуют возможности загрузки исходных данных из текстового файла, сохранения результатов в файл, а также распечатки подробных действий реализации алгоритма (то есть логирование).

Спасибо за внимание! Если будут вопросы — рад на них ответить.

Источник

aaronjwood / BinarySearchTree.cs

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

using System ;

using System . Diagnostics ;

namespace BinarySearchTree

class Node

public int value ;

public Node left ;

public Node right ;

>

class Tree

public Node insert ( Node root , int v )

if ( root == null )

root = new Node ( ) ;

root . value = v ;

>

else if ( v < root . value )

root . left = insert ( root . left , v ) ;

>

else

root . right = insert ( root . right , v ) ;

>

return root ;

>

public void traverse ( Node root )

if ( root == null )

return ;

>

traverse ( root . left ) ;

traverse ( root . right ) ;

>

>

class BinarySearchTree

static void Main ( string [ ] args )

Node root = null ;

Tree bst = new Tree ( ) ;

int SIZE = 2000000 ;

int [ ] a = new int [ SIZE ] ;

Console . WriteLine ( » Generating random array with values. » , SIZE ) ;

Random random = new Random ( ) ;

Stopwatch watch = Stopwatch . StartNew ( ) ;

for ( int i = 0 ; i < SIZE ; i ++ )

a [ i ] = random . Next ( 10000 ) ;

>

watch . Stop ( ) ;

Console . WriteLine ( » Done. Took seconds » , ( double ) watch . ElapsedMilliseconds / 1000.0 ) ;

Console . WriteLine ( ) ;

Console . WriteLine ( » Filling the tree with nodes. » , SIZE ) ;

watch = Stopwatch . StartNew ( ) ;

for ( int i = 0 ; i < SIZE ; i ++ )

root = bst . insert ( root , a [ i ] ) ;

>

watch . Stop ( ) ;

Console . WriteLine ( » Done. Took seconds » , ( double ) watch . ElapsedMilliseconds / 1000.0 ) ;

Console . WriteLine ( ) ;

Console . WriteLine ( » Traversing all nodes in tree. » , SIZE ) ;

watch = Stopwatch . StartNew ( ) ;

bst . traverse ( root ) ;

watch . Stop ( ) ;

Console . WriteLine ( » Done. Took seconds » , ( double ) watch . ElapsedMilliseconds / 1000.0 ) ;

Console . WriteLine ( ) ;

Console . ReadKey ( ) ;

>

>

>

Источник