Двоичное дерево, алгоритмы основных операций

Дерево — это абстрактный тип данных для иерархического хранения элементов. За исключением элемента во главе дерева, каждый элемент структуры имеет родителя (parent element) и ноль или более дочерних элементов (children element). Для придания древовидной структуре большей наглядности ее элементы изображаются в виде овалов или прямоугольников, а связи между ними — в виде прямых линий.

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

Если узел u является родителем узла v, то можно говорить, что v является дочерним узлом u. Два узла, выступающие дочерними элементами по отношению к одному и тому же родителю, будут называться сестрами/братьями. Предком узла может быть либо родительский узел, либо предок родителя этого узла. И наоборот, можно сказать, что v является потомком узла u, если u является предком v.

Бинарным деревом (binary tree) называется упорядоченное дерево, в котором каждый из узлов имеет максимум два дочерних элемента. дочерних элемента. Дочерние элементы в таких узлах имеют маркировку «левый» и «правый» (left child и right child). Эти элементы упорядочены таким образом, что левый меньше правого.

Естественным способом реализации бинарного дерева является использование связной структуры. При таком подходе каждый узел v дерева Т представляется объектом со ссылками на элемент, хранящийся в v, и на объекты, связанные с дочерними и родительскими элементами узла v (рис. 44).

Рис. 44. Представление двоичного дерева

 

Определим два класса: узел дерева TreeNode и дерево SearchTree

public class TreeNode

{ private TreeNode left, right, parent;

private int dat;

public TreeNode Left

{ get { return left; }

set { left = value; } }

public TreeNode Right

{ get { return right; }

set { right = value; } }

public TreeNode Parent

{ get { return parent; }

set { parent = value; } }

public int Dat

{ get { return dat; }

set { dat = value; } }

public TreeNode(int v, TreeNode p)

{ Dat = v; Left = null; Right = null; Parent = p; } }

 

Конструктор класса формирует узел с определенными данными, заданным предком и пустыми потомками.

public class SearchTree

{

private data[] rez;

private TreeNode root; private int num;

public TreeNode Root

{ get { return root; }

set { root = value; } }

public int Num

{

get { return num; }

set { num = value; }

}

public data[] Rez

{

get { return rez; }

set { rez = value; }

}

public SearchTree() { Root = null; Num = 0; Rez = new data[10]; }

public bool isEmpty() { return (Root == null); }

public TreeNode find(int el)

{

TreeNode current = Root;

while (current!= null)

if (el == current.Dat.shifr)

return (current);

else

current = el <current.Dat.shifr? current.Left:current.Right;

return (null); }

public data prisv(data r)

{ data r1; r1 = r; return r1; }

public data[] inorder(TreeNode n)

{ data b;

b.shifr = 0;7

b.name = "";

if (n!= null)

{inorder(n.Left);

b = prisv(n.Dat);

Rez[Num]=b; Num++;

inorder(n.Right);

}

else { }return Rez;

}

public TreeNode insert(data el)

{ TreeNode x, current, parent;

Num=0;

current = Root;

parent = null;

while (current!= null)

{ if (el.shifr == current.Dat.shifr) return (current);

parent = current;

current = el.shifr <current.Dat.shifr? current.Left:current.Right; }

x = new TreeNode(el, parent);

if (parent!= null)

if (x.Dat.shifr<parent.Dat.shifr)

parent.Left=x;

else

parent.Right=x;

else

Root = x;

return (x); }

public void remove(TreeNode z)

{ TreeNode x, y, t;

if (z == null) return;

if (z.Left == null || z.Right == null)

y = z;

else

{ y = z.Right;

while (y.Left!= null) y = y.Left; }

if (y.Left!= null)

x = y.Left;

else

x = y.Right;

if (x!= null) x.Parent=y.Parent;

if (y.Parent!= null)

{ t = y.Parent;

if (y == t.Left)

t.Left=x;

else

t.Right=x; }

else

Root = x;

if (y!= z)

{ y.Left=z.Left;

if (y.Left!= null)

{ t = y.Left; t.Parent=y; }

y.Right=z.Right;

if (y.Right!= null)

{ t = y.Right; t.Parent=y; }

y.Parent=z.Parent;

if (z.Parent!= null)

{ t = z.Parent; if (z == t.Left)

t.Left=y;

else

t.Right=y; }

else

Root = y;

z = null; }

else y = null; } }}

Класс содержит поле root, которое указывает на корень двоичного дерева поиска (объект класса TreeNode). Конструктор класса формирует двоичное дерево с пустым корнем. Дерево пусто, если поле root пустое. Чтобы найти заданный элемент dat, поиск начинается с корня и затем продолжается вниз до узла, содержащего dat. В каждом узле n сравнивается el с элементом dat узла n. Если el меньше, чем dat узла n, то поиск продолжается, начиная с левого потомка узла n, если el больше, чем dat узла n, то поиск продолжается, начиная с правого потомка n, в противном случае возвращается адрес узла n (и задача решена). Путь от корневого узла вниз до el называется путем поиска для el. Обход двоичного дерева — это процесс, при котором каждый узел посещается только один раз. Метод inorder выполняет специальную форму обхода, известную как симметричный обход.

Стратегия заключается сначала в симметричном обходе левого поддерева, затем посещения корня и потом в симметричном обходе правого поддерева. Узел посещается путем добавления его данных в поле rez – массив данных. Размер этого массива –свойство num.

Для включения нового элемента в двоичное дерево вначале нужно определить его точное положение — а именно предок, который должен быть заменен путем отслеживания пути поиска элемента, начиная с корня. Кроме сохранения указателя n на текущий узел мы будем хранить указатель р на предка узла n. Таким образом, когда n достигнет некоторого узла, р будет указывать на узел, который должен стать предком нового узла.

Удаление узла, у которого есть не более чем один непустой потомок, является сравнительно простой задачей — устанавливается ссылка от предка узла на потомка. Однако ситуация становится гораздо сложнее, если у подлежащего удалению узла есть два непустых потомка: предок узла может быть связан с одним из потомков, а что делать с другим? Решение может заключаться не в удалении узла из дерева, а скорее в замене элемента, содержащегося в нем, на потомка этого элемента, а затем в удалении узла-потомка.