Бинарное дерево на C#

 
0
 
.NET
ava
gypehot19 | 16.11.2016, 18:17
Прошу помощи. Необходимо реализовать на C# бинарное дерево поиска, вставку элементов поочередно из исходного массива (меньшее - в левую ветку, большее - в правую ветку), реализовать возможность удаления элемента и в конечный массив забить поочередно элементы из заполненного дерево, предварительно отсортировав по возрастанию.
Застопорилась сразу после вставки элемента, никакие идеи в голову не приходят.
И да, если одинаковые элементы добавляются несколько раз, то увеличивать их счетчик в узле на 1. Тоже не знаю как сделать.
Вот что есть:

class Program
    {
        static void Main(string[] args)
        {
            int[] mas_begin = new int[21] { 9, 8, 7, 3, 2, 1, 11, 13, 14, 15, 19, 20, 21, 5, 6, 4, 10, 12, 17, 16, 18 };
            int[] mas_end = new int[21];

            BinaryTree<int> tree = new BinaryTree<int>();
            Console.WriteLine("Поочередно введены числа:");            
            foreach (int d in mas_begin)
            {
                tree.Add(d);
                Console.Write(d + " ");
            }

            Console.ReadLine();
        }
    }

    /// <summary>
    /// класс для одной любой вершины дерева
    /// </summary>
    class Node<T> where T : IComparable
    {
        public Node<T> Left { get; set; }
        public Node<T> Right { get; set; }
        public T value { get; set; }

        public Node(T value)
        {
            this.value = value;
        }
    }

    /// <summary>
    /// общий класс для дерева из всех элементов
    /// </summary>
    class BinaryTree<T> where T: IComparable
    {
        public Node<T> root;

        /// <summary>
        /// добавление элемента
        /// </summary>
        public void Add(T new_value)
        {
            if (root == null) //инициализация корня, если его еще нет
            {
                root = new Node<T>(new_value);
                return;
            }
            AddNew(root, new_value); //выборка куда добавлять следующий элемент, если корень уже есть
        }

        /// <summary>
        /// выборка куда добавлять новый элемент
        /// </summary>
        private static void AddNew(Node<T> this_node, T new_value)
        {
            if (this_node.value.CompareTo(new_value) < 0) //если новое значение меньше текущего, идем по левой ветке
            {
                if (this_node.Left == null) //если левой ветки не было, то создаем ее и оставляем новый элемент здесь
                    this_node.Left = new Node<T>(new_value);
                else //если левая ветка уже есть, то входим в нее и продолжаем дальше искать пустую ветку
                    AddNew(this_node.Left, new_value);
            }
            else //если новое значение больше текущего, идем по правой ветке
            {
                if (this_node.Right == null) //если правой ветки не было, то создаем ее и оставляем новый элемент здесь
                    this_node.Right = new Node<T>(new_value);
                else //если правая ветка уже есть, то входим в нее и продолжаем дальше искать пустую ветку
                    AddNew(this_node.Right, new_value);
            }
        }
    }
Ответы (3)
ava
chupachups | 17.11.2016, 15:38 (Отредактирован 17.11.2016 15:40) #
класс ветки неполный, надо дополнить методом добавления и свойством счетчика:

/// <summary>
/// класс для одной любой вершины дерева
/// </summary>
class Node<T> where T : IComparable
{
    public Node<T> Left { get; private set; }
    public Node<T> Right { get; private set; }
    public int Count { get; private set; }
    public T Value { get; private set; }

    public Node(T value)
    {
        this.Value = value;
    }

    /// <summary>
    /// добавление элемента
    /// </summary>
    public void Add(T value)
    {
        int res = this.Value.CompareTo(value);
        if (res == 1)
        {
            // увеличить счетчик
            this.Count++;
        }
        if (res < 0) //если новое значение меньше текущего, идем по левой ветке
        {
            if (this.Left == null) //если левой ветки не было, то создаем ее и оставляем новый элемент здесь
                this.Left = new Node<T>(value);
            else //если левая ветка уже есть, то входим в нее и продолжаем дальше искать пустую ветку
                this.Left.Add(value);
        }
        else //если новое значение больше текущего, идем по правой ветке
        {
            if (this.Right == null) //если правой ветки не было, то создаем ее и оставляем новый элемент здесь
                this.Right = new Node<T>(value);
           else //если правая ветка уже есть, то входим в нее и продолжаем дальше искать пустую ветку
                this.Right.Add(value);
        }
    }
}

ava
chupachups | 17.11.2016, 15:44 (Отредактирован 17.11.2016 15:49) #
тогда само дерево будет таким:

/// <summary>
/// общий класс для дерева из всех элементов
/// </summary>
class BinaryTree<T> where T : IComparable
{
    public Node<T> root;

    /// <summary>
    /// добавление элемента
    /// </summary>
    public void Add(T new_value)
    {
        if (root == null) //инициализация корня, если его еще нет
            root = new Node<T>(new_value);
        else
            root.Add(new_value); //выборка куда добавлять следующий элемент, если корень уже есть
    }
}

ava
gypehot19 | 18.11.2016, 21:06 #
Спасибо!
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить