Симметричный обход

Лабораторная работа № 5

«ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ «БИНАРНОГО ДЕРЕВА»»

Цель работы: исследовать и изучить АТД «дерево».

Задача работы: овладеть навыками составления структур АТД «дерево» и написания программ по исследованию АТД «дерево» на любом языке программирования.

Порядок работы:

1. изучить описание лабораторной работы;

2. по заданию, данному преподавателем, разработать структуру АТД «дерево»;

3. написать программу на языке С#;

4. отладить программу;

5. решить задачу;

6. оформить отчет.

Краткая теория

Пример создания дерева.

namespace WindowsFormsApplication1

{

public partial class Обход: Form

{

public List<TreeElement> arrayList = new List<TreeElement>();

public TreeElement myStruct;

public struct TreeElement

{

public int left;

public int right;

public bool mark;

public string val;

}

public Обход()

{

InitializeComponent();

}

public int Priam(int v)

{

textBox1.Text = textBox1.Text +' '+ arrayList[v].val;

if (arrayList[v].left!= -1) Priam(arrayList[v].left);

if (arrayList[v].right!= -1) Priam(arrayList[v].right);

return 0;

}

public int Obrat(int v)

{

if (arrayList[v].left!= -1) Obrat(arrayList[v].left);

if (arrayList[v].right!= -1) Obrat(arrayList[v].right);

textBox1.Text = textBox1.Text + ' ' + arrayList[v].val;

return 0;

}

public int Simetr(int v)

{

if (arrayList[v].left!= -1) Obrat(arrayList[v].left);

textBox1.Text = textBox1.Text + ' ' + arrayList[v].val;

if (arrayList[v].right!= -1) Obrat(arrayList[v].right);

return 0;

}

private void button1_Click(object sender, EventArgs e)

{

myStruct.left = 1;

myStruct.right = 2;

myStruct.mark = false;

myStruct.val = "a";

arrayList.Add(myStruct);

myStruct.left = 3;

myStruct.right = 4;

myStruct.mark = false;

myStruct.val = "b";

arrayList.Add(myStruct);

myStruct.left = 5;

myStruct.right = 6;

myStruct.mark = false;

myStruct.val = "c";

arrayList.Add(myStruct);

myStruct.left = -1;

myStruct.right = -1;

myStruct.mark = false;

myStruct.val = "d";

arrayList.Add(myStruct);

myStruct.left = 7;

myStruct.right = -1;

myStruct.mark = false;

myStruct.val = "f";

arrayList.Add(myStruct);

myStruct.left = -1;

myStruct.right = -1;

myStruct.mark = false;

myStruct.val = "g";

arrayList.Add(myStruct);

myStruct.left = -1;

myStruct.right = -1;

myStruct.mark = false;

myStruct.val = "k";

arrayList.Add(myStruct);

myStruct.left = -1;

myStruct.right = -1;

myStruct.mark = false;

myStruct.val = "l";

arrayList.Add(myStruct);

Прямой обход дерева

private void button2_Click(object sender, EventArgs e)

{

textBox1.Text = textBox1.Text + '\r' + '\n' + "Прямой обход ";

Priam(0);

}

Обратный обход

private void button3_Click(object sender, EventArgs e)

{

textBox1.Text = textBox1.Text + '\r' + '\n' + "Обратный обход ";

Obrat(0);

}

Симметричный обход

private void button4_Click(object sender, EventArgs e)

{

textBox1.Text = textBox1.Text + '\r' + '\n' + "Симметричный обход ";

Simetr(0);

}