Предположим, что в дерево, приведенное выше, следует включить узел с ключом 11. Путь поиска места включения будет таким: корень ® 16 ® 3 ® 10 ® пусто. Так как 11 > 10, то узел следует включить в правую ветвь узла 10. Если ключи следуют в порядке строгого возрастания или убывания, то дерево принимает облик списка. При этом один из указателей каждого узла имеет нулевое значение, то есть он не работает и, следовательно, является архитектурным излишеством. Пусть узлы поступают в порядке: 1, 2, 3, 4, 5. Дерево будет вырожденным, оно имеет вид списка и понапрасну расходует указатели на левые ветви.
Очевидно, что крона дерева будет тем более ветвистой, чем ближе к равномерному закону распределения вероятности будет приближаться входная последовательность ключевых полей. На следующем рисунке показано дерево, которое считается полным. Оно содержит 32 узла (считая корень) и обладает рядом замечательных свойств. Обратите внимание на некоторые из них: симметрию структуры, количество узлов в каждом ярусе дерева (степени двойки), местоположение узлов с нечетными значениями ключей. Известно, что время поиска элемента в дереве с хорошей кроной значительно меньше, чем в линейном списке.
Применим объектно-ориентированный подход к задаче хранения информации в бинарном дереве. Рассмотрим задачу хранения информацию о людях в бинарном дереве. Так как элементы дерева должны иметь уникальные ключевые поля, введем в класс Man новое поле данных—номер паспорта человека (или его табельный номер). Таким образом, класс Man изменится незначительно по сравнению с предыдущими заданиями. Вам придется лишь добавить код в конструктор копирования и свойство Name. Выполните это самостоятельно.
public class Man
{
private int id, age;
private string name;
public static int maxName = 15, maxAge = 200;
public int ID // Свойство, обеспечивающее доступ к переменной id
{
get { return id; }
set { id = value; }
}
public int Age // Свойство, защищающее переменную age
{
get { return age; }
set
{
if (value < 0 || maxAge < value)
throw new ArgumentOutOfRangeException ("age = " + value, "Wrong");
else
age = value;
}
}
public string Name // Свойство, защищающее переменную name
{
get { /* Вставьте код */ }
set
{
name = value;
/* Вставьте код, который укорачивает имя, если оно содержит больше maxName символов */
}
}
public Man()
{
id = age = 0;
name = "N/A";
}
public Man (int i, string n, int a)
{
id = i;
name = n;
age = a;
}
public Man (Man m)
{
/* Вставьте код, который копирует все поля данных объекта m */
}
public override string ToString()
{
return string.Format ("{0}.\t{1}; Age: {2}", id, name.PadRight(maxName), age);
}
}
Для удобства пользования деревом создадим класс Node (узел дерева), объединяющий ссылку на информационную часть узла (Man man) и ссылки на левую и правую ветви дерева. Здесь вам надо доработать свойства, обеспечивающие доступ к скрытым переменным left и right класса Node и создать код двух конструкторов.
public class Node
{
private Man man;
private Node left, right;
public Node Left
{
/* Разработайте свойство, дающее доступ к полю left */
}
public Node Right
{
/* Разработайте свойство, дающее доступ к полю right */
}
public Man ManRef { get { return man; } }
public Node()
{
/* Разработайте код конструктора */
}
public Node (Man m)
{
/* Разработайте код конструктора копирования */
}
}
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.