VPF::Деревья "высаживаю" ... - Форум программистов

lioness

Дата 15.8.2006, 14:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 82
Регистрация: 27.7.2006

Репутация: нет
Всего: нет

Ха! Рекурсию-то можно изобразить, если ползти по дереву только ВНИЗ.
А вот если надо пробежаться от начала до конца, не пропуская ни одного узла и прыгая то налево, то направо, да переходя на одном уровне г-о-р-и-з-о-н-т-а-л-ь-н-о. Я уж не говорю, подняться вверх по дереву. Чего-то рекурсией не выходит.

Попыталась просто распечатать в цикле на форме узлы (что-то похожее как было в статье FindByValue )

Код


            lblMessage.Text = "";
            int index = 1;
            foreach (NodeList<int> nl in currNode)
            {
                lblMessage.Text = index +". Niveau -> ";
                  foreach (Node<int> currN in nl)
                      lblMessage.Text = lblMessage.Text + currNode.Value + "   ";
                index++;
            }

но требует GetEnumerator для BinaryTreeNode<int>

Хотя мне по заданию бинарное дерево вообще не подойдет. Я хотела c ним только потренироваться, раз уж майкрософт не предлагает системных "деревьевых" классов.

А нужно мне компактное дерево. Вот такое ->

http://www.cs.ucla.edu/~sliu/papers/Ctree-TechReport.pdf

Правда, мне уже тут сказали: не извращайтесь, девушка. Берите ArrayList smile

и делайте с ним, что хотите smile

mr.DUDA

Дата 15.8.2006, 14:59 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 110
Всего: 232

По поводу деревьев, есть несколько алгоритмов обхода: прямой (pre-order), симметричный (in-order) и обратный (post-order). Все три очень легко реализуются с помощью итераторов. Если чем-то может помочь, вот исходник:

Program.cs

Код

using System;
using System.Collections.Generic;


namespace Task1
{
    // синтаксический сахар
    using StringTree = BinaryTree<string>;

    class Program
    {
        static void Main(string[] args)
        {
            StringTree A = new StringTree("A");
            StringTree B = A.Left = new StringTree("B");
            StringTree C = A.Right = new StringTree("C");
            StringTree D = B.Left = new StringTree("D");
            StringTree E = B.Right = new StringTree("E");
            StringTree F = E.Left = new StringTree("F");
            StringTree G = E.Right = new StringTree("G");

            // проверим
            Console.WriteLine("Pre-order enumeration:");
            foreach (StringTree node in A.PreOrderIterator())
                Console.Write(node.Value + " ");

            Console.WriteLine(Environment.NewLine + "In-order enumeration:");
            foreach (StringTree node in A.InOrderIterator())
                Console.Write(node.Value + " ");

            Console.WriteLine(Environment.NewLine + "Post-order enumeration:");
            foreach (StringTree node in A.PostOrderIterator())
                Console.Write(node.Value + " ");


            Console.WriteLine();
        }
    }
}

BinaryTree.cs

Код

using System;
using System.Collections.Generic;

namespace Task1
{
    /// <summary>
    /// Двоичное дерево с произвольными значениями в узлах.
    /// </summary>
    /// <typeparam name="T">Тип значения в узле дерева</typeparam>
    public class BinaryTree<T>
    {
        public BinaryTree(T value)
        {
            this.Value = value;
        }

        // открытые свойства

        #region Value

        private T _value;
        /// <summary>
        /// Значение для данного узла дерева.
        /// </summary>
        public T Value
        {
            get
            {
                return _value;
            }
            set
            {
                _value = value;
            }
        }

        #endregion

        #region Left

        private BinaryTree<T> _left;
        /// <summary>
        /// Левое поддерево.
        /// </summary>
        public BinaryTree<T> Left
        {
            get
            {
                return _left;
            }
            set
            {
                _left = value;
            }
        }

        #endregion

        #region Right

        private BinaryTree<T> _right;
        /// <summary>
        /// Правое поддерево.
        /// </summary>
        public BinaryTree<T> Right
        {
            get
            {
                return _right;
            }
            set
            {
                _right = value;
            }
        }

        #endregion


        // перечисление

        #region PreOrderIterator()

        public IEnumerable<BinaryTree<T>> PreOrderIterator()
        {
            // сама вершина
            yield return this;
            // обход левой ветки
            if (this.Left != null)
            {
                foreach (BinaryTree<T> node in this.Left.PreOrderIterator())
                    yield return node;
            }
            // обход правой ветки
            if (this.Right != null)
            {
                foreach (BinaryTree<T> node in this.Right.PreOrderIterator())
                    yield return node;
            }
        }

        #endregion

        #region InOrderIterator()

        public IEnumerable<BinaryTree<T>> InOrderIterator()
        {
            // обход левой
            if (this.Left != null)
            {
                foreach (BinaryTree<T> node in this.Left.InOrderIterator())
                    yield return node;
            }
            // сама вершина
            yield return this;
            // обход правой
            if (this.Right != null)
            {
                foreach (BinaryTree<T> node in this.Right.InOrderIterator())
                    yield return node;
            }
        }

        #endregion

        #region PostOrderIterator()

        public IEnumerable<BinaryTree<T>> PostOrderIterator()
        {
            // обход левой
            if (this.Left != null)
            {
                foreach (BinaryTree<T> node in this.Left.PostOrderIterator())
                    yield return node;
            }
            // правой
            if (this.Right != null)
            {
                foreach (BinaryTree<T> node in this.Right.PostOrderIterator())
                    yield return node;
            }
            // сама вершина
            yield return this;
        }

        #endregion
    }
}

--------------------

lioness

Дата 15.8.2006, 15:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 82
Регистрация: 27.7.2006

Репутация: нет
Всего: нет

Значит, все-таки только "перечисление".

Да мне бинарное дерево совсем не походит. Мне бы СТree, а в статье о CTree http://www.cs.ucla.edu/~sliu/papers/Ctree-TechReport.pdf - кодов ни грамма. Только алгоритмы. smile

А у меня как раз "сплав" подобной информации из записей и одни записи могут иногда вкладыватся друг в друга "узлами" и все это записать в формате XML.

А напарник-немец, с которым нам сейчас данными перебрасываться, говорит фиг с ним, с деревом ентим.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »