Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

как создать бинарное дерево на С#

8.3K
04 марта 2012 года
roman@
63 / / 10.11.2007
подскажите как создать бинарное дерево на С# без библиотек, если возможно с комментариями
10K
05 марта 2012 года
Cybernetic
106 / / 22.07.2009
Создаешь структуру "Вершина дерева", которая имеет две ссылки на структуры "Вершина дерева" (то есть на себя же), а так же можешь вписывать значения, которые должна хранить вершина.
Потом создаешь класс "Дерево", в котором хранишь ссылку на элемент типа "Вершина дерева". Это будет корнем. А от корня уже можно плясать как хочешь.
Код специально не пишу, потому что вроде как тут все понятно, если тебе знакомы понятия "класс" и "ссылка".

Собственно, так создается бинарное дерево на многих (всех?) ООП-языках.
8.3K
05 марта 2012 года
roman@
63 / / 10.11.2007
я то понимаю суть дерева, реализовать не знаю как (
10K
05 марта 2012 года
Cybernetic
106 / / 22.07.2009
 
Код:
class Node
{
    public Node Left {get; set; }
    public Node Right {get; set; }
    public int Value {get; set; }
}



 
Код:
class Tree
{
    private Node _root;
   
    Tree()
    {
        _root = new Node();
    }
}


Вот создание дерева. Что здесь непонятного? Или непонятно, как его рекурсивно обходить?
8.3K
05 марта 2012 года
roman@
63 / / 10.11.2007
не ясно как можно добавлять новые элементы и чтобы при добавлены элементов создавалось дерево, а не только в одну сторону добавлялись элементы.
10K
06 марта 2012 года
Cybernetic
106 / / 22.07.2009
Цитата: roman@
не ясно как можно добавлять новые элементы и чтобы при добавлены элементов создавалось дерево, а не только в одну сторону добавлялись элементы.


Слишком абстрактно говоришь. Я сам должен догадываться, какую задачу тебе нужно решить?
В интернетах и учебниках есть множество примеров. Самый известный и простой из них - построение бинарного дерева поиска. На вход поступает массив чисел, по нему строится дерево(по принципу: в вершине элемент, в левой подвершине меньшее число, в правой - большее).
Пример: 9,2,7,8,4, 0. Последовательно их засовываем в дерево по шагам:

Код:
1) 9

2) 9
   |
   2

3)  9
   /  \
  2    7

4)   9
    /  \
   2    7
         \
          8

5)     9
      /  \
     2    7
      \    \
       4    8

6)     9
      / \
     2   7
    / \   \
   0   4   8


Теперь понятно? Или код надо написать? Если и код не сможешь написать, лучше сразу скажи, какая у тебя задача, на ней будем рассматривать проблемы.
8.3K
06 марта 2012 года
roman@
63 / / 10.11.2007
задача научиться работать с бинарными деревьями на С # но без всяких библиотек, а самому уметь написать. В сети ищу примеры, чтобы проанализировать, но к сожалению все что находил то с использованием List и т.п.


очень благодарен, что ты откликнулся)
8.3K
06 марта 2012 года
roman@
63 / / 10.11.2007
пытаюсь создать дерево, чтобы последовательно заполнять все ветки новыми элементами которые добавляются
10K
07 марта 2012 года
Cybernetic
106 / / 22.07.2009
Выдалась свободная минутка, написал примерчик кода, реализацию того, о чем раньше говорил. Надеюсь, это будет полезной пищей для размышления.

Создается класс-generic для бинарного дерева, туда можно впихнуть все, что можно сравнить(реализует интерфейс IComparable), а также создается конкретный класс (для демонстрации обхода дерева). Рекомендуется код вставить в студию и поизучать(его там тупо будет легче читать).


Код:
/// <summary>
/// Класс для одной вершины дерева
/// </summary>
/// <typeparam name="T">Элемент дерева. Сюда можно вставить всё, что можно сравнить =)</typeparam>
class Node<T> where T : IComparable
{
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
    public T Element { get; set; }

    public Node(T element)
    {
        Element = element;
    }
}

/// <summary>
/// Общее дерево для сортировки элементов
/// </summary>
/// <typeparam name="T">Элемент дерева. Сюда можно вставить всё, что можно сравнить =)</typeparam>
class Tree<T> where T: IComparable
{
    /// <summary>
    /// Постоянная ссылка на корень. Нужна, чтобы не "потярть" дерево и служит точкой отсчет при рекурсивных обходах
    /// </summary>
    protected Node<T> _root;

    /// <summary>
    /// Метод служит для добавления нового элемента в дерево
    /// </summary>
    /// <param name="newElement">Новый элемент</param>
    public void AddElement(T newElement)
    {
        if (_root == null) //Добавление первого элемента, своего рода инициализация дерева
        {
            //Так как дерево пустое, то просто инициализируем корень, без всяких проверок и вычислений
            _root = new Node<T>(newElement);
            return;
        }
        //Если корень уже есть, то заходим в него и начинаем вычислять, куда добавить текущий элемент
        AddElementRecursion(_root, newElement);
    }
    /// <summary>
    /// Рекурсивный метод для добавления элемента в дерево
    /// Рассматривается текущая вершина currentNode и анализируется, куда надо добавлять новый элемент, в левое или правое поддерево
    /// </summary>
    /// <param name="currentNode">Текущая вершина</param>
    /// <param name="newElement">Добавляемый элемент</param>
    private static void AddElementRecursion(Node<T>currentNode, T newElement)
    {
        if (currentNode.Element.CompareTo(newElement) < 0) //Если новый элемент меньше текущего
        {
            // То заходим в его правую ветку
            if (currentNode.Right == null) // Если правой ветки не было, то создаем правого детёныша, и, соответственно, заканчивается добавление
                currentNode.Right = new Node<T>(newElement);
            else //Если же правая ветка есть, то входим в нее, и повторяем такую же процедуру
                AddElementRecursion(currentNode.Right, newElement);
        }
        else //Иначе, если новый элемент больше или равен текущему
        {
            // То заходим в его левую ветку
            if ( currentNode.Left == null ) // Если левой ветки не было, то создаем левого детёныша, и, соответственно, заканчивается добавление
                currentNode.Left = new Node<T>(newElement);
            else //Если же левая ветка есть, то входим в нее, и повторяем такую же процедуру
                AddElementRecursion(currentNode.Left, newElement);
        }

    }

    /// <summary>
    /// Пример использования дерева. Поиск минимального элемента
    /// </summary>
    /// <returns>Найденный минимальный элемент</returns>
    public T GetMinElement()
    {
        //указываем, что надо начинать искать с корня, и уходим в рекурсию
        return GetMinElementRecursion(_root);
    }
    /// <summary>
    /// Рекурсивный метод для поиска минимального элемента в дереве
    /// Рассматривается текущая вершина currentNode и анализируется, где дальше надо искать минимальный элемента, в левом или правом поддереве
    /// </summary>
    /// <param name="currentNode">Текущая вершина</param>
    /// <returns>Найденный минимальный элемент</returns>
    private static T GetMinElementRecursion(Node<T> currentNode)
    {
            if (currentNode.Left == null)
            return currentNode.Element;
        else
            return GetMinElementRecursion(currentNode.Left);
    }
}

/// <summary>
/// Конкретизированное дерево на тип double, расширяем предыдущее дерево
/// </summary>
class TreeDoubleType : Tree<double>
{
    /// <summary>
    /// Пример рекурсивного обхода дерева. Поиск суммы всех элементив
    /// </summary>
    /// <returns>Найденная сумма всех элементов</returns>
    public double GetSum()
    {
        //Инициализация суммы
        double sum = 0;
        //Уход в рекурсию для поиска суммы
        GetSumRecursion(_root, ref sum);
        return sum;
    }
    /// <summary>
    /// Рекурсивный метод для поиска минимального элемента в дереве
    /// Рассматривается текущая вершина currentNode и анализируется, где дальше надо искать минимальный элемента, в левом или правом поддереве
    /// <param name="currentNode">Текущая вершина</param>
    /// <param name="sum">Текущая сумма</param>
    /// </summary>
    private static void GetSumRecursion(Node<double> currentNode, ref double sum)
    {
        //Прибавляем элемент из текущей вершины
        sum += currentNode.Element;
        //Считаем сумму для левого поддерева
        if (currentNode.Left != null)
            GetSumRecursion(currentNode.Left, ref sum);
        //Считаем сумму для левого поддерева
        if (currentNode.Right != null)
            GetSumRecursion(currentNode.Right, ref sum);
    }
}




//Далее использование дерева, вставлять куда необходимо :)

            //Массив, взятый из головы для примера
            double[] doubleArray = new [] {1, 5, -1.4, 7, 3, 0, 4, -1, 6, 10, 8.4, 5, -7, -6, 5, 3, 7, -2};

            //Создание дерева
            TreeDoubleType tree = new TreeDoubleType();
           
            //Заполнение дерева
            foreach (double d in doubleArray)
                tree.AddElement(d);

            //Работа с деревом
            double min = tree.GetMinElement();
            double sum = tree.GetSum();

            Console.WriteLine("Минимальный элемент дерева: {0}", min);
            Console.WriteLine("Сумма элементов дерева: {0}", sum);

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог