Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Общие вопросы по .NET и C# > от С++ к C#

Автор: ZuTa 2.3.2011, 20:30

Здравствуйте!

Подскажите, пожалуйста, как реализовать бинарное дерево в C# ?
Например в С++ можно написать такую структуру :

Код


struct node
{
int n; 
node *left;
node *right; 
}

Автор: Экскалупатор 2.3.2011, 21:20

ZuTa, точно так же. только без "*". и не struct а class.

Код


public class node
    {
        public int n;
        public node left;
        public node right;
    }

но это не серьезно, надо что бы все поля были скрытыми, доступ к ним через свойства/методы... и прочие штуки что бы код стал безопаснее и кошернее.

Автор: ZuTa 2.3.2011, 21:24

Спасибо!
Учту ваши пожелания smile

Автор: ZuTa 2.3.2011, 22:50

Экскалупатор,

Код


class Node
    {
        #region Fields
        private int n;
        private Node left;
        private Node right;
        private Node level;
        #endregion

        #region Properties
        public int N
        {
            get { return n; }
            set { n = value; }
        }
        public Node Left
        {
            get { return left; }
            set { left = value; }
        }
        public Node Right
        {
            get { return right; }
            set { right = value; }
        }

        public Node Level
        {
            get { return level; }
            set { level = value; }
        }

        #endregion

        #region Contructors
        public Node()
        {
            n = 0;
            left = null;
            right = null;
            level = null;
        }
        public Node(int n)
        {
            this.n = n;
            left = null;
            right = null;
            level = null;
        }
        #endregion

        #region Methods
        #endregion
    }

Автор: Экскалупатор 2.3.2011, 22:54

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

Добавлено через 10 минут и 11 секунд
и еще.
на мой взгляд совершенно лишним является конструктор без параметров. потому что очевидно что узел дерева не может не содержать значения, а делать много узлов со значением 0 не имеет смысла(но это имхо). ну и не совсем понятно назначение Node Level. это уровень чего? и почему там храниться ссылка на какой то узел?

Автор: ZuTa 2.3.2011, 23:18

Экскалупатор, та я писал функцию для уже готового бинарного дерева (т.е. я не заботился о том как и куда добавлять - это делали другие).

На счет, конкруктора без параметров, согласен.
А level - это уже особенность моей задачи.

Но у меня возник вопрос : а как посчитать сколько памяти используется если задано дерево с грубиной T и N узлами ?(например, для С++ структуры, которую я написал в первом посте)

Добавлено через 13 минут и 6 секунд

Код


struct node
{
    int n;            
    node *left;        
    node *right;    
};

Читал когда-то, что указатель в памяти занимает 4 байта
Если это правда, значит структура будет занимать 3*4=12 байтов

правильно ли это ?

Автор: jonie 3.3.2011, 08:30

Цитата(ZuTa @ 2.3.2011, 23:18

)

Читал когда-то, что указатель в памяти занимает 4 байта
Если это правда, значит структура будет занимать 3*4=12 байтов

указатель занимает в памяти не меньше sizeof(void*). Может больше - например указатели на функцию-член класса.. В стандарте С++ не определен размер указателя - зависит от архитектуры.

И размер структуры будет sizeof(node). Т.к. в мире c++ существует выравнивание данных, что регулируется компилятором, если не задано явно используя #pragma pack(XXX)

Аналогично, можно используя sizeof() в C# (в unsafe части кода) прикинуть размер... но всё это лишь приблизительная оценка будет. На самом деле сколько занимать памяти будет класс или структура никто не скажет.

Автор: Экскалупатор 3.3.2011, 08:46

не совсем. есть же еще ссылка на саму структуру, плюс методы если они есть(конструктор, деструктор и пр.) тоже занимают место, но они обычно создаются в одном экземпляре на все объекты классов. в шарпе еще больше, там ссылка размещается в стеке + в куче выделяется память под все элементы класса + служебная информация.

Цитата(ZuTa @ 2.3.2011, 22:18

)

Читал когда-то, что указатель в памяти занимает 4 байта

в 32-битной ОС да.

Цитата(ZuTa @ 2.3.2011, 22:18

)

та я писал функцию для уже готового бинарного дерева

а мне показалось что мы обсуждаем именно само дерево а не работу с ним, по крайней мере весь код это само дерево, и никаких функций не было еще...