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

Тема в разделе ".NET", создана пользователем leftTheHaskel, 11 июн 2012.

Наш партнер Genesis Hackspace
  1. leftTheHaskel

    leftTheHaskel Гость

    Добрый день! Пишу словарь на основе префиксного динамического дерева) На данный момент пытаюсь осуществить добавление элемента с помощью рекурсии. Вот код
    Код (Text):
    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>();
    }
    }

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

    MrRockchip Гость

    не дови на меня :)
     
  3. kertio

    kertio Гость

    Ну для начала, ты ведь описал функцию как private Wordd AddElement(string s, Wordd node), соответственно и вернуть нужно Wordd.
     
  4. polishuchka

    polishuchka Гость

    Может уже и поздно, но вдруг кому-то еще пригодится. Ета программа работает. Для проверки добавлено обход дерева.
    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);
    }
    }
     

Поделиться этой страницей