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

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

  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);
    }
    }
     

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