C# Рекурсивное Дабовление Элементов В Дерево

  • Автор темы leftTheHaskel
  • Дата начала
L

leftTheHaskel

#1
Добрый день! Пишу словарь на основе префиксного динамического дерева) На данный момент пытаюсь осуществить добавление элемента с помощью рекурсии. Вот код
Код:
namespace Slovar
{
public partial class Form1 : Form
{
Wordd tree;//дерево

public Form1()
{
InitializeComponent();
tree = new Wordd();// создаём новый элемент типа Wordd
}

private void button1_Click(object sender, EventArgs e)
{
Wordd temp = new Wordd();
temp.Slovo = textBox2.Text;
temp.Perevod = textBox1.Text;
AddElement(temp.Slovo,tree);//функция добавления
}

private Wordd AddElement(string s, Wordd node)
{ 
if (s.Length==0) return null;//если слово кончилось то return 
else{
for (int i = 0; i < s.Length; i++)
{
string bykva = s.Substring(0, 1);
node.Bykva = bykva;
if (node.qwer.Count == 0) { node.qwer.Add(node); s=s.Substring(1, s.Length - 1); node.Bykva = s.Substring(0, 1); node.qwer[i].Bykva =node.Bykva; }
if ((bykva) == Convert.ToString(node.qwer[i].Bykva))
{

s = s.Substring(1, s.Length - 1);
node.qwer[i].Add(node);
}
else
{
Wordd w = new Wordd();
w.Bykva = s.Substring(0, 1);
s = s.Substring(1, s.Length - 1);
node.qwer[i].qwer.Add(w);
w = AddElement(s, node);

}
}
}

}
return что-то; //:D вот тут я не в курсе
} 
}

public class Wordd
{

public string Slovo;
public string Perevod;
public string Bykva;
public List<Wordd> qwer;

public Wordd()
{
qwer = new List<Wordd>();
}
}

}
Не знаю как дальше написать...Запутался! Нужна ваша помощь! За ранее спасибо!
 
P

polishuchka

#4
Может уже и поздно, но вдруг кому-то еще пригодится. Ета программа работает. Для проверки добавлено обход дерева.
public partial class Form1 : Form
{
Wordd Slovnyk;
public Form1()
{
InitializeComponent();
}
// Определение из Википедии
// Префиксное дерево — абстрактный тип данных (АТД), структура данных, позволяющая хранить ассоциативный массив,
// ключами которого являются строки. В отличие от бинарных деревьев, в листьях дерева не хранится ключ.
// Значение ключа можно получить просмотром всех родительских узлов, каждый из которых хранит один или несколько
// символов алфавита. Корень дерева связан с пустой строкой. Таким образом, потомки узла имеют общий префикс,
// откуда и произошло название данного АТД. Значения, связанные с ключом, обычно не связаны с каждым узлом,
// а только с листьями и, возможно, некоторыми внутренними узлами.


public class Wordd
{
public string Slovo;
public string Bukva;
public string Perevod;
public List<Wordd> vuzly;
public Wordd(string bukva, string slovo, string perevod) // Конструктор с параметрами
{
vuzly = new List<Wordd>();
Slovo = slovo;
Bukva = bukva;
Perevod = perevod;
}
// Метод для внесения елемента в дерево
public void AddElement(ref string newSlovo,string slovo, string newPerevod, Wordd vuzol)
{
if (vuzol == null) return;
if (newSlovo == null) return;
if (newSlovo == "") return;
for (int i = 0; i < newSlovo.Length; i++)
{
string newBukva = newSlovo.Substring(0, 1);
bool kl = false;
for (int j = 0; j < vuzol.vuzly.Count; j++)
{
if (vuzol.vuzly[j].Bukva == newBukva)
{
// нужний узел нашелся
if (newSlovo == "") return;
newSlovo = newSlovo.Substring(1, newSlovo.Length - 1);
vuzol = vuzol.vuzly[j];
AddElement(ref newSlovo, slovo, newPerevod, vuzol);
kl = true;
}
}
if (!kl) // Готового узла нет, надо его создать
// Поля Slovo и Perevod заполняем только для тех узлов, путь к которим полностью содержит слово
{ string ps, pps,bukva;
if (newSlovo.Length ==1) { ps = slovo; pps = newPerevod; } else { ps = ""; pps = ""; }
if (slovo.Length >= 1) bukva = newSlovo.Substring(0, 1); else bukva = "";
// Создаем новий узел, используя конструктор с параметрами
Wordd newVuzol = new Wordd(bukva,ps, pps);
// Цепляем его к коллекции узлов
vuzol.vuzly.Add(newVuzol);
// Убираем обработаную букву
newSlovo = newSlovo.Substring(1, newSlovo.Length - 1);
vuzol = newVuzol;
// Вносим елемент в дерево
AddElement(ref newSlovo, slovo, newPerevod, vuzol);
kl = true;
}
}
}
public void ObhodDereva( Wordd vuzol)
{
if (vuzol == null) return;
int i=0;
while ( i < vuzol.vuzly.Count)
{
MessageBox.Show("Узел дерева. Буква:"+vuzol.vuzly.Bukva +" Слово:"+vuzol.vuzly.Slovo +" Перевод:"+vuzol.vuzly.Perevod );
if (vuzol.vuzly.vuzly.Count > 0) ObhodDereva(vuzol.vuzly);
i++;
}
}

}


private void buttonAdd_Click(object sender, EventArgs e)
{
// При первом входе создадим словать
if (Slovnyk == null) Slovnyk = new Wordd("", "","");
string newSlovo = textBox1.Text;
string newPerevod = textBox2.Text;
Slovnyk.AddElement(ref newSlovo,newSlovo , newPerevod, Slovnyk);

}

private void buttonObhodDereva_Click(object sender, EventArgs e)
{
Slovnyk.ObhodDereva( Slovnyk);
}
}