Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

 
3 / 23

---

96 
Листинг 4.16. Вызов метода HeapCreate() 
private void buttonCreate_Click(object sender, Even-
tArgs e) 
{ 
int L = textBox1.Lines.Count(); 
myTour.a = new int[L]; 
myTour.arr = new MyTour.Node[0]; 
for (int i = 0; i < L; i++) 
if (textBox1.Lines[i] != "") 
myTour.a[i] = Con-
vert.ToInt32(textBox1.Lines[i]); 
myTour.SetDelta(ClientRectangle.Width – 
panel1.Width); 
myTour.head = my-
Tour.HeapCreate(ClientRectangle.Height); 
myTour.Draw(); 
g.DrawImage(myTour.bitmap, ClientRectangle); 
} 
Метод DrawNode(), представленный листингом 4.17, реализует рекур-
сивный алгоритм построения изображения дерева и выполняет прорисовку 
отдельных узлов с выводом в них значений ключей. В этом же листинге 
представлен метод Draw(), из которого производится вызов DrawNode(). 
Листинг 4.17. Метод рисования узла 
void DrawNode(Node p) // 
рекурсивное рисование узлов
{ 
if (p.left!=null) 
g.DrawLine(MyPen, p.x,p.y,p.left.x,p.left.y); 
if (p.right != null) 
g.DrawLine(MyPen, p.x, p.y, p.right.x, 
p.right.y); 
4 / 23

---

97 
MyBrush.Color = Color.LightYellow; 
g.FillEllipse(MyBrush, p.x - radius,
p.y - radius, 2 * radius, 2 * radius); 
g.DrawEllipse(MyPen, p.x - radius, p.y - radius,
2 * radius, 2 * radius); 
string s = Convert.ToString(p.data); 
SizeF size = g.MeasureString(s, MyFont); 
g.DrawString(s, MyFont, Brushes.Black, 
p.x - size.Width / 2, p.y - size.Height / 2); 
if (p.left != null) 
DrawNode(p.left); 
if (p.right != null) 
DrawNode(p.right); 
} 
public void Draw() // 
рисование дерева 
{ 
using (g = Graphics.FromImage(bitmap)) { 
Color cl = Color.FromArgb(255, 255, 255); 
g.Clear(cl); 
MyPen = Pens.Black; 
if (head != null) 
DrawNode(head); 
// 
вывод упорядоченной последовательности узлов 
int L = arr.Length; 
for (int i = 0; i < L; i++) { 
g.FillEllipse(MyBrush, arr[i].x - radius,
arr[i].y - radius, 2 * radius, 2 * ra-
dius); 
5 / 23

---

98 
g.DrawEllipse(MyPen, arr[i].x - radius,
arr[i].y - radius, 2 * radius, 2 * ra-
dius); 
string s = Convert.ToString(arr[i].data); 
SizeF size = g.MeasureString(s, MyFont); 
g.DrawString(s, MyFont, Brushes.Black, 
arr[i].x-size.Width/2,
arr[i].y - size.Height/2); 
} 
} 
} 
После построения дерева-пирамиды начинается этап формирования 
упорядоченной последовательности. Он состоит из отдельных шагов, на каж-
дом из которых узел с минимальным значением ключа удаляется из вершины 
пирамиды и добавляется в отсортированную последовательность узлов arr. 
Это действие требует полной перестройки пирамиды, поскольку значение, 
удаляемое из пирамиды, представлено соответствующим узлом на каждом ее 
уровне. Алгоритм перестройки пирамиды осуществляет рекурсивный спуск 
до нижнего уровня по ветви дерева, состоящей из узлов со значениями, рав-
ными минимальному значению ключа. Узел-лист с минимальным значением 
удаляется присваиванием ссылке на него значения null, а во все подобные 
узлы на вышележащих уровнях записывается минимальное из значений в их 
дочерних узлах. Перестройка пирамиды производится методом Competi-
tion
() класса MyTour, единственным параметром которого является указа-
тель на вершину дерева-пирамиды, передаваемый по ссылке. 
Метод, выполняющий перестройку дерева-пирамиды, приведен в лис-
тинге 4.18.