Секреты LINQ. Автогенерируемые свойства. Инициализаторы объектов и коллекций, страница 11

¨  Параметр T шаблона BinaryTree<T> определяет тип данных, которые будут хранится в узлах дерева.

¨  Вложенный generic-класс Node<T> реализует функциональность узла дерева. Каждый объект Node<T> хранит ссылку на данные, соответствующие текущему узлу (тип данных определяется параметром T), и две ссылки на (левый и правый) узлы, прикрепленные к текущему узлу.

¨  Единственным полем данных класса BinaryTree<T> является ссылка на корневой узел дерева root.

public class BinaryTree<T> where T : IComparable<T>

{

public class Node<T> where T : IComparable<T>

{

public T data;

public Node<T> left, right;

public Node(T data) { this.data = data; }

}

Node<T> root;

public IEnumerable<T> OrderedSet { get { return GetAll(root); } }

void Add(T item, ref Node<T> node)

{

if (node == null)

node = new Node<T>(item);

else if (item.CompareTo(node.data) < 0)

Add(item, ref node.left);

else

Add(item, ref node.right);

}

IEnumerable<T> GetAll(Node<T> node)

{

if (node.left != null)

{

foreach (T item in GetAll(node.left))

yield return item;

}

yield return node.data;

if (node.right != null)

{

foreach (T item in GetAll(node.right))

yield return item;

}

}

void Print(Node<T> item, int depth, int offset)

{

if (item == null)

return;

Console.CursorLeft = offset;

Console.CursorTop = depth;

Console.Write(item.data);

if (item.left != null)

Print("/", depth + 1, offset - 1);

Print(item.left, depth + 2, offset - 3);

if (item.right != null)

Print("\\", depth + 1, offset + 1);

Print(item.right, depth + 2, offset + 3);

}

void Print(string s, int depth, int offset)

{

Console.CursorLeft = offset;

Console.CursorTop = depth;

Console.Write(s);

}

public void Add(T item) { Add(item, ref root); }

public void AddRange(params T[] items)

{

foreach (var item in items)

Add(item);

}

public void Print() { Print (root, 0, Console.WindowWidth / 2); }

}

Ограничитель where T : IComparable<T> говорит компилятору о том, что не любой тип данных может быть задан в качестве параметра шаблона BinaryTree<T>, а только тип, выполняющий интерфейс IComparable.

Вы знаете, что бинарное дерево поиска должно быть упорядочено по ключу и эти ключи при формировании кроны дерева необходимо сравнивать. Поэтому требование уметь сравнивать объекты, которые надо хранить в дереве, совершенно необходимо для типа, который подается на вход шаблона BinaryTree<T>. Говорят, что шаблон настраивается на определенный тип T.

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

static void TestBinaryTree()

{

Console.Clear ();

string line = new string('\u2500', 22);

Console.WriteLine(line + "Test BinaryTree<int>\nPress any key.");

BinaryTree<int> tree = new BinaryTree<int>();

tree.AddRange(16, 8, 24, 4, 12, 20, 28, 2, 6, 10, 14, 18, 22, 26, 30, 1, 3, 5, 7, 9, 11,

13, 15, 17, 19, 21, 23, 25, 27, 29, 31);

tree.Print();

Console.WriteLine("\n\nNot formatted BinaryTree<int>\n");

foreach (var item in tree.OrderedSet)

Console.Write(item + ", ");

}

¨  Рекурсивный метод Print показывает, как управлять позициями данных, выводимых в консольное окно. С его помощью мы показывает структуру дерева.

¨  Метод GetAll с помощью оператора yield создает итеративный блок и накапливает информацию об узлах дерева в generic-коллекции IEnumerable<T>.

¨  С помощью свойства OrderedSet универсального класса BinaryTree<T> мы получаем эту коллекцию и выводим ее содержимое простым перечислением, без позиционирования на экране узлов дерева.