Бинарные деревья си шарп

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 ( ) ;

>

>

>

Источник

Бинарное дерево — двоичное дерево поиска. Основные операции с бинарными деревьями (C#, Java)

Бинарное дерево представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух дочерних узлов. Как правило, первый называется родительским узлом или корнем дерева (root), а дочерние узлы называются левым и правым наследниками.

Бинарное дерево либо является пустым, либо состоит из данных и двух поддеревьев, каждое из которых может быть пустым. Каждое поддерево в свою очередь тоже является деревом. Узлы без наследников принято называть листьями.

Для такого дерева должны выполняться следующие условия:

1. Левое и правое поддерево так же являются бинарными деревьями;
2. У всех узлов левого поддерева произвольного узла x значения ключей данных меньше значения ключа данных самого узла x ;
3. У всех узлов правого поддерева произвольного узла x значения ключей данных больше либо равны значению ключа данных самого узла x .

Основные операции с бинарным деревом

Основными операциями с бинарными деревьями являются добавление элемента в дерево, удаление элемента и поиск элемента в дереве. Сложность каждой из этих операций O(log\,n) в лучшем случае, и O(n) в худшем. Зависит от сбалансированности дерева.

Пример сбалансированного бинарного дерева (лучший случай):

Пример несбалансированного бинарного дерева (худший случай): Добавление элемента в дерево

При добавлении элемента x в дерево проверяем значение текущего узла.

• Если значение добавляемого элемента x меньше значения текущего узла, спускаемся к левому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим левое поддерево как текущий узел и повторим сначала.
• Если значение добавляемого элемента x больше или равно значению текущего узла, спускаемся к правому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим правое поддерево как текущий узел и повторим сначала.

Пример добавления элемента в двоичное дерево

Создадим бинарное дерево с корневым элементом 33 и добавим в него элементы в следующей последовательности: 5, 35, 1, 20, 99, 17, 18, 19, 31, 4. Получим бинарное дерево такого вида:

Поиск элемента в бинарном дереве

Поиск начинаем с родительского элемента. Допустим, мы ищем значение 18 (обозначим его за x ). Алгоритм поиска будет иметь следующий вид:

Поиск несуществующего элемента сведется к тому, что вы нарветесь на несуществующий узел и это будет означать, что искомого элемента в дереве нет.

Удаление элемента из бинарного дерева

Удаление листьев

Если удаляемый элемент является листом, то просто удаляем у его родителя ссылку на этот элемент (например на значение 31). Удалим его.

Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева

После удаления 31 элементом, имеющим левое поддерево, но не имеющим правого поддерева является элемент 20. Удалим его из дерева:

1. Указываем, что родителем элемента 17 теперь будет элемент 5.
2. Указываем, что правым потомком элемента 5 теперь является элемент 17.

После удаления значений 31 и 20 дерево приобретает такой вид:

Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева

1. Удалим элемент 17. Присвоим его правому поддереву в качестве родителя элемент 5.
2. Элементу 5 укажем, что его правым поддеревом теперь является элемент 18.

Получим следующую картину:

Удаляем узел, имеющий поддеревья с обеих сторон

Первый случай

Правое поддерево не имеет потомка.

Чтобы иметь возможность рассмотреть этот случай, добавим элемент 34 в дерево: Удалим элемент 35. Для этого:

1. Правому поддереву (99) присвоим в качестве родителя элемент 33;
2. Ему же в качестве левого поддерева присваиваем элемент 34;
3. Элементу 34 указываем нового родителя — 99;
4. Родителю удаляемого элемента (33) указываем, что его правым поддерево теперь является элемент 99.

Второй случай

Правое поддерево имеет своих потомков.

Удаляем элемент 5. Первым потомком (одновременно самым левым — минимальным в его поддереве) элемента 5 является элемент 18:

1. Элементу 18 в качестве левого узла присвоим элемент 1;
2. Элементу 1 присвоим 18 как родителя;
3. Элементу 33 (родителю удаляемого элемента) укажем в качестве левого дочернего узла элемент 18;
4. Элементу 18 указываем в качестве родителя элемент 33 (родитель удаляемого элемента).

Дерево приобретает такой вид:

Если минимальный левый элемент имеет правых потомков и при это не является первым потомком удаляемого элемента, то его правый потомок присваивается родителю минимального элемента правого поддерева.

В своем коде я использовал нерекурсивный механизм удаления.

Существуют и другие механизмы удаления. Визуализировать свое дерево вы можете на ресурсе usfca.edu. Вы заметите, что алгоритм удаления там отличается от описанного выше.

Код класса дерева на Java в моем исполнении имеет следующий вид:

package main; import java.util.ArrayList; import java.util.List; public class Tree> < private T val; private Tree left; private Tree right; private Tree parent; private ListlistForPrint = new ArrayList<>(); public T val() < return val; >public Tree left() < return left; >public Tree right() < return right; >public Tree parent() < return parent; >public Tree(T val, Tree parent) < this.val = val; this.parent = parent; >public void add(T. vals) < for(T v : vals)< add(v); >> public void add(T val) < if(val.compareTo(this.val) < 0)< if(this.left==null)< this.left = new Tree(val, this); >else if(this.left != null) this.left.add(val); > else < if(this.right==null)< this.right = new Tree(val, this); >else if(this.right != null) this.right.add(val); > > private Tree _search(Tree tree, T val) < if(tree == null) return null; switch (val.compareTo(tree.val))< case 1: return _search(tree.right, val); case -1: return _search(tree.left, val); case 0: return tree; default: return null; >> public Tree search(T val) < return _search(this, val); >public boolean remove(T val) < //Проверяем, существует ли данный узел Treetree = search(val); if(tree == null) < //Если узла не существует, вернем false return false; >Tree curTree; //Если удаляем корень if(tree == this) < if(tree.right!=null) < curTree = tree.right; >else curTree = tree.left; while (curTree.left != null) < curTree = curTree.left; >T temp = curTree.val; this.remove(temp); tree.val = temp; return true; > //Удаление листьев if(tree.left==null && tree.right==null && tree.parent != null) < if(tree == tree.parent.left) tree.parent.left = null; else < tree.parent.right = null; >return true; > //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева if(tree.left != null && tree.right == null) < //Меняем родителя tree.left.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.left; >else if(tree == tree.parent.right) < tree.parent.right = tree.left; >return true; > //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева if(tree.left == null && tree.right != null) < //Меняем родителя tree.right.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.right; >else if(tree == tree.parent.right) < tree.parent.right = tree.right; >return true; > //Удаляем узел, имеющий поддеревья с обеих сторон if(tree.right!=null && tree.left!=null) < curTree = tree.right; while (curTree.left != null) < curTree = curTree.left; >//Если самый левый элемент является первым потомком if(curTree.parent == tree) < curTree.left = tree.left; tree.left.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > //Если самый левый элемент НЕ является первым потомком else < if (curTree.right != null) < curTree.right.parent = curTree.parent; >curTree.parent.left = curTree.right; curTree.right = tree.right; curTree.left = tree.left; tree.left.parent = curTree; tree.right.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > > return false; > private void _print(Tree node) < if(node == null) return; _print(node.left); listForPrint.add(node.val); System.out.print(node + " "); if(node.right!=null) _print(node.right); >public void print() < listForPrint.clear(); _print(this); System.out.println(); >@Override public String toString() < return val.toString(); >>

Поработать с классом можно следующим образом:

public static void main(String[] args) < //Создадим дерево с корневым элементом 33 Treetree = new Tree<>(33, null); tree.add(5, 35, 1, 20, 4, 17, 31, 99, 18, 19); //Распечатаем элементы дерева tree.print(); //Удалим корень tree.remove(33); tree.remove(17); tree.print(); //Проверяем элементы дерева System.out.println(tree); System.out.println(tree.left()); System.out.println(tree.left().left()); System.out.println(tree.right().left()); >

К слову, на Java такой код особого смысла писать нет, т.к. там существуют классы TreeSet и TreeMap, представляющие собой деревья.

На C# код класса бинарного дерева может иметь такой вид:

/* * User: Николай Разиов * Date: 29.10.2018 */ using System; using System.Collections.Generic; namespace Trees < public class BinaryTreewhere T : IComparable  < private BinaryTreeparent, left, right; private T val; private List listForPrint = new List(); public BinaryTree(T val, BinaryTree parent) < this.val = val; this.parent = parent; >public void add(T val) < if(val.CompareTo(this.val) < 0)< if(this.left==null)< this.left = new BinaryTree(val, this); > else if(this.left != null) this.left.add(val); > else< if(this.right==null)< this.right = new BinaryTree(val, this); > else if(this.right != null) this.right.add(val); > > private BinaryTree _search(BinaryTree tree, T val) < if(tree == null) return null; switch (val.CompareTo(tree.val))< case 1: return _search(tree.right, val); case -1: return _search(tree.left, val); case 0: return tree; default: return null; >> public BinaryTree search(T val) < return _search(this, val); >public bool remove(T val) < //Проверяем, существует ли данный узел BinaryTreetree = search(val); if(tree == null) < //Если узла не существует, вернем false return false; >BinaryTree curTree; //Если удаляем корень if(tree == this) < if(tree.right!=null) < curTree = tree.right; >else curTree = tree.left; while (curTree.left != null) < curTree = curTree.left; >T temp = curTree.val; this.remove(temp); tree.val = temp; return true; > //Удаление листьев if(tree.left==null && tree.right==null && tree.parent != null) < if(tree == tree.parent.left) tree.parent.left = null; else < tree.parent.right = null; >return true; > //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева if(tree.left != null && tree.right == null) < //Меняем родителя tree.left.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.left; >else if(tree == tree.parent.right) < tree.parent.right = tree.left; >return true; > //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева if(tree.left == null && tree.right != null) < //Меняем родителя tree.right.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.right; >else if(tree == tree.parent.right) < tree.parent.right = tree.right; >return true; > //Удаляем узел, имеющий поддеревья с обеих сторон if(tree.right!=null && tree.left!=null) < curTree = tree.right; while (curTree.left != null) < curTree = curTree.left; >//Если самый левый элемент является первым потомком if(curTree.parent == tree) < curTree.left = tree.left; tree.left.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > //Если самый левый элемент НЕ является первым потомком else < if (curTree.right != null) < curTree.right.parent = curTree.parent; >curTree.parent.left = curTree.right; curTree.right = tree.right; curTree.left = tree.left; tree.left.parent = curTree; tree.right.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > > return false; > private void _print(BinaryTree node) < if(node == null) return; _print(node.left); listForPrint.Add(node.val); Console.Write(node + " "); if(node.right!=null) _print(node.right); >public void print() < listForPrint.Clear(); _print(this); Console.WriteLine(); >public override string ToString() < return val.ToString(); >> >

Код примерно такой же, только для C# он будет гораздо полезнее.

Исходники проектов можно взять здесь:

Источник

C# Binary Search Tree Implementation

This example shows how to implement a Binary Search Tree using C#. A tree whose nodes have at most 2 child nodes is called a binary tree. we name them the left and right child because each node in a binary tree can have only 2 children.
A sample binary tree:

Tree Traversals (PreOrder, InOrder, PostOrder)

All source code is below.
Node Class:

class Node < public Node LeftNode < get; set; >public Node RightNode < get; set; >public int Data < get; set; >>

BinaryTree Class:

class BinaryTree < public Node Root < get; set; >public bool Add(int value) < Node before = null, after = this.Root; while (after != null) < before = after; if (value < after.Data) //Is new node in left tree? after = after.LeftNode; else if (value >after.Data) //Is new node in right tree? after = after.RightNode; else < //Exist same value return false; >> Node newNode = new Node(); newNode.Data = value; if (this.Root == null)//Tree ise empty this.Root = newNode; else < if (value < before.Data) before.LeftNode = newNode; else before.RightNode = newNode; >return true; > public Node Find(int value) < return this.Find(value, this.Root); >public void Remove(int value) < this.Root = Remove(this.Root, value); >private Node Remove(Node parent, int key) < if (parent == null) return parent; if (key < parent.Data) parent.LeftNode = Remove(parent.LeftNode, key); else if (key >parent.Data) parent.RightNode = Remove(parent.RightNode, key); // if value is same as parent's value, then this is the node to be deleted else < // node with only one child or no child if (parent.LeftNode == null) return parent.RightNode; else if (parent.RightNode == null) return parent.LeftNode; // node with two children: Get the inorder successor (smallest in the right subtree) parent.Data = MinValue(parent.RightNode); // Delete the inorder successor parent.RightNode = Remove(parent.RightNode, parent.Data); >return parent; > private int MinValue(Node node) < int minv = node.Data; while (node.LeftNode != null) < minv = node.LeftNode.Data; node = node.LeftNode; >return minv; > private Node Find(int value, Node parent) < if (parent != null) < if (value == parent.Data) return parent; if (value < parent.Data) return Find(value, parent.LeftNode); else return Find(value, parent.RightNode); >return null; > public int GetTreeDepth() < return this.GetTreeDepth(this.Root); >private int GetTreeDepth(Node parent) < return parent == null ? 0 : Math.Max(GetTreeDepth(parent.LeftNode), GetTreeDepth(parent.RightNode)) + 1; >public void TraversePreOrder(Node parent) < if (parent != null) < Console.Write(parent.Data + " "); TraversePreOrder(parent.LeftNode); TraversePreOrder(parent.RightNode); >> public void TraverseInOrder(Node parent) < if (parent != null) < TraverseInOrder(parent.LeftNode); Console.Write(parent.Data + " "); TraverseInOrder(parent.RightNode); >> public void TraversePostOrder(Node parent) < if (parent != null) < TraversePostOrder(parent.LeftNode); TraversePostOrder(parent.RightNode); Console.Write(parent.Data + " "); >> >

Sample Application:

BinaryTree binaryTree = new BinaryTree(); binaryTree.Add(1); binaryTree.Add(2); binaryTree.Add(7); binaryTree.Add(3); binaryTree.Add(10); binaryTree.Add(5); binaryTree.Add(8); Node node = binaryTree.Find(5); int depth = binaryTree.GetTreeDepth(); Console.WriteLine("PreOrder Traversal:"); binaryTree.TraversePreOrder(binaryTree.Root); Console.WriteLine(); Console.WriteLine("InOrder Traversal:"); binaryTree.TraverseInOrder(binaryTree.Root); Console.WriteLine(); Console.WriteLine("PostOrder Traversal:"); binaryTree.TraversePostOrder(binaryTree.Root); Console.WriteLine(); binaryTree.Remove(7); binaryTree.Remove(8); Console.WriteLine("PreOrder Traversal After Removing Operation:"); binaryTree.TraversePreOrder(binaryTree.Root); Console.WriteLine(); Console.ReadLine();

Program output:

Источник