Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/26: Рейтинг темы: голосов - 26, средняя оценка - 4.50
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
1

Как сохранить структуру бинарного дерева в файл и ее же загрузить в программу

13.04.2012, 15:48. Просмотров 4887. Ответов 19
Метки нет (Все метки)

Подскажите пожалуйста, как сохранить и загрузить структуру бинарного дерева в отдельный файл?

Допустим, в программе я создал бинарное дерево. Теперь нужно его сохранить в отдельный файл (какой-нибудь test.dat).
Видел где-то, но для Дельфи, один мэн создавал метод.. а в методе прописывал обход дерева, и после всего прохода, записывал в файл... И после он этот метод вызывал с передачей имени нужного дерева.

А вот как в C# это делается? Что-то в толк не возьму..
Если есть где-нибудь источники с этой информацией, прошу поделиться.

Аналогично и для загрузки. При выборе нужного файла, выводилось на экран готовое бинарное дерево. И после этого можно было бы производить дальнейшую его обработку. Т.е. из файла передавались не значения дерева... а именно готовая структура.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2012, 15:48
Ответы с готовыми решениями:

Вывод и запись бинарного дерева в XML файл
Имеется XML файл <?xml version="1.0" encoding="utf-8" ?> <tree> <node...

Вывод бинарного дерева в виде дерева
Помогите пожалуйста вывести дерево в консоль в виде дерева. Саму структуру я...

Как копировать каталог с подкаталогами и сохранить при этом структуру каталогов?
Как, при копировании, копировать каталог с подкаталогами, и сохранить при этом...

Как сохранить структуру дерева?
Здравствуйте, такой вопрос: у меня есть дерево (TreeView) я в него...

Как сохранить структуру дерева?
Здравствуйте, такой вопрос: программирую на Visual Basic .NET, у меня есть...

19
Psilon
Master of Orion
Эксперт .NET
6013 / 4866 / 902
Регистрация: 10.07.2011
Сообщений: 14,477
Записей в блоге: 5
Завершенные тесты: 4
13.04.2012, 17:24 2
jjohndavis, вот, почитайте. Написано на дельфи, но алгоритм по-русски ясно объяснен, кода почти нету, в основном алгоритмы, так что поймете (стр.130)
1
Вложения
Тип файла: rar RodStivens.rar (3.89 Мб, 144 просмотров)
Konctantin
940 / 744 / 171
Регистрация: 12.04.2009
Сообщений: 1,700
13.04.2012, 18:18 3
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var treeNode = new TreeNode("321");
treeNode.Nodes.Add("456");
treeNode.Nodes.Add("789");
 
var formater = new BinaryFormatter();
 
using (var stream = File.Create("binary.bin"))
{
    formater.Serialize(stream, treeNode);
}
 
using (var stream = File.Open("binary.bin", FileMode.Open))
{
    var tree = (TreeNode)formater.Deserialize(stream);
}
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
14.04.2012, 14:42  [ТС] 4
Psilon, спасибо за книгу! Буду изучать.
Konctantin, за подсказку об использовании Серилизации спасибо. Но сам код не понял, как будто разные куски кода собрали воедино. Видимо там чего-то не хватает... существенного, чтобы компилятор позволил серилизовать.
0
Konctantin
940 / 744 / 171
Регистрация: 12.04.2009
Сообщений: 1,700
14.04.2012, 15:08 5
это полностью рабочий пример, который вы даже не удосужились применить.
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
14.04.2012, 15:49  [ТС] 6
Konctantin, прошу прощения, если оскорбил своими заявлениями. Но я пробовал вставить этот код к себе, но компилятор не принял.

Помогите пожалуйста разобраться на примере моего проекта: куда вставлять этот работающий код?
В общих чертах проект выглядит так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
namespace AVL
{   public partial class Form1 : Form
    {   public Form1() {InitializeComponent();}
 
        public partial class AvlTree
        {
            private AvlNode _root; //глоб.переменная
 
          public class AvlNode //Структура листа дерева
            {
                public AvlNode Parent;
                public AvlNode Left;
                public AvlNode Right;
                public int Value;
                public int Balance;
            }
           
           /*методы обработки AVL-дерева*/
           public void Insert(int value) {...} //Метод добавления нового узла
           private void InsertBalance(AvlNode node, int balance) {...} //балансировка дерева после добавления
           /*Методы вращения дерева*/
           private AvlNode RotateLeft(AvlNode node) {...}
           private AvlNode RotateRight(AvlNode node) {...}
           private AvlNode RotateLeftRight(AvlNode node) {...}
           private AvlNode RotateRightLeft(AvlNode node) {...}
 
           private static void Replace(AvlNode target, AvlNode source) {...} //Замена узлов (используется в методе Delete)
           public bool Delete(int value) {...} //Удаление узла
           private void DeleteBalance(AvlNode node, int balance) {...} //Балансировка после удаления
           public bool Search(int value) {...} //Поиск узла в дереве
           public void Clear() {...} //Удаление дерева
           public string Printtree() {...} //Метод обхода дерева, используется для вызова в button1.click
           public void Traversal(AvlNode node) {...} //Сама рекурсия обхода, используется в методе Printtree
       }
 
        public static int[] StringToInt32Array(string st) {...} //конвектор int <- string
 
        private void button1_Click(object sender, EventArgs e)
        {
            AvlTree NewTree = new AvlTree(); //Создаем объект типа дерева
 
            //Вводим элементы в дерево
            string s = textBox1.Text; 
            int[] x = StringToInt32Array(s);
            for (int i = 0; i < x.Length; i++)
            {NewTree.Insert(x[i]);}
            //*********************
 
            label1.Text = NewTree.Printtree(); //Распечатка дерева на экране
        }
              
        /*Незакончено*/
        private void saveFileDialog1_FileOk(object sender, System.ComponentModel.CancelEventArgs e)
        {
            string myfileName = saveFileDialog1.FileName;
        }
 
        //Через кнопку откроем saveFileDialog1
        private void button2_Click(object sender, System.EventArgs e)
        {
             saveFileDialog1.Filter = ".bin|.bin";
             saveFileDialog1.ShowDialog();
        }
 
   }
}
Я вам буду очень признателен!
0
Psilon
Master of Orion
Эксперт .NET
6013 / 4866 / 902
Регистрация: 10.07.2011
Сообщений: 14,477
Записей в блоге: 5
Завершенные тесты: 4
14.04.2012, 17:12 7
jjohndavis, офк неважно, но если вы сдаете преподавателю и не хотите "ошибок" в коде, то возможно в методе
C#
1
2
public void Traversal(AvlNode node) {...} 
//Сама рекурсия обхода, используется в методе Printtree
стоит объявить его private?
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
14.04.2012, 17:20  [ТС] 8
Psilon, точно!!! Исправлю Правда, это все мелочи (но правило хорошего тона)... к такому преподаватель придираться не будет. Мне б с сохранением и загрузкой разобраться...
0
Konctantin
940 / 744 / 171
Регистрация: 12.04.2009
Сообщений: 1,700
14.04.2012, 17:38 9
давайте пойдем иным путем:

1) класс BinaryFormatter, перейдя по ссылке, можно посмотреть что это такое, там же мы увидим в каком пространстве имен находится данный класс. исходя из этого. чтобы компилятор не ругался подключим данное пространство имен:
C#
1
using System.Runtime.Serialization.Formatters.Binary;
2) Для того, чтобы применить это дело в вашем коде, немножко подумаем вместе, что и куда вставлять:

C#
1
2
3
var treeNode = new TreeNode("321");
treeNode.Nodes.Add("456");
treeNode.Nodes.Add("789");
создание и заполнение дерева, это у вас и так есть.

далее, для того чтобы сериализовать/десериализовать данный объект нам надо создать экземпляр класса BinaryFormatter, сделать это можно несколькими способами:
а) Объявить его как поле класса:
C#
1
2
3
4
5
6
7
8
9
public partial class Form1 : Form
{   
    private BinaryFormatter formatter;
    
    public Form1() 
    {
        InitializeComponent();
        this.formatter = new BinaryFormatter();
     }
б) либо создавать его при каждом событии:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
// serialise to file 
using (var stream = File.Create("binary.bin"))
{
    var formater = new BinaryFormatter();
    formater.Serialize(stream, treeNode);
}
 
// deserialise from file
using (var stream = File.Open("binary.bin", FileMode.Open))
{
    var formater = new BinaryFormatter();
    var tree = (TreeNode)formater.Deserialize(stream);
}
далее вам надо немножко подумать. чтобы понять куда это вставлять, но думаю тут и так все понятно...

Добавлено через 4 минуты
Ах да, вы используете свой собственный класс AvlNode, так вот, для того чтобы работала сериализация/десериализация - необходимо чтобы данный класс был помечен как [Serializable]
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
14.04.2012, 18:28  [ТС] 10
Как я понимаю, нужно сделать вот так:
Если использовать метод (б), то

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class AvlTree
        {
            private AvlNode _root;
 
            [Serializable]
            public class AvlNode {...} //структура листа
                                  
                                  /*методы*/
                                 
                                 //И в этот же класс AvlNode создать еще 2 метода
                                 public void Save()
                                 {
                                      // serialise to file 
                                      using (var stream = File.Create("binary.bin"))
                                   {
                                        var formater = new BinaryFormatter();
                                        formater.Serialize(stream, treeNode);
                                   }
                                 }
 
                                 public void Load() {} //аналогично для загрузки
И в Button1.Click, к примеру, после создания дерева, вызвать NewTree.Save().

Так? Хмм.... кажись не очень. Хотя было б логично.
Если этот код кидать в классе AvlTree, то компилятор ругается... не может прочесть var, using.

Добавлено через 21 минуту
Везде ругается на using...
А если использовать метод (а), то ... ровным счетом ничего явного не происходит. Ведь binarformatter все-равно где-то вызывать нужно?
0
Konctantin
940 / 744 / 171
Регистрация: 12.04.2009
Сообщений: 1,700
15.04.2012, 00:21 11
Зачем туда это пихать?
Давайте еще раз.
Покажите ваш класс AvlNode, чтобы было ясно что с ним делать, и что это у вас такое.
Методы сохранения и загрузки можно прилепить к соответствующим кнопкам.
Если этот код кидать в классе AvlTree, то компилятор ругается... не может прочесть var, using.
а кто вас учил его кидать в класс?
Везде ругается на using...
покажите полный кусок кода, ну не верю я что он просто так ругается... это мистика.
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
15.04.2012, 08:51  [ТС] 12
Вот... Да, на using перестало ругаться, компилятор выдает только 4 ошибки:
строка 45. Ошибка1 - Элемент "File" не существует в текущем контексте
строка 48. Ошибка2 - Элемент "treeNode" не существует в текущем контексте. (Видимо нужно заменить на мой AvlNode класс? Но даже на это выдает ту же самую ошибку).
строка 55. Ошибка3 - Элемент "File" не существует в текущем контексте
строка 55. Ошибка4 - Элемент "FileMode" не существует в текущем контексте.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
...
using System.Runtime.Serialization.Formatters.Binary;
 
namespace AVL
{public partial class Form1 : Form
    {public Form1()  {InitializeComponent();}
 
        public partial class AvlTree //общий класс
        {
            private AvlNode _root; //глобальная переменная
 
            [Serializable]
            public class AvlNode //структура узла дерева
            {
                public AvlNode Parent;
                public AvlNode Left;
                public AvlNode Right;
                public int Value;
                public int Balance;
            }
 
            /*методы*/
            {...}
        }
 
        //кнопка ввода элементов в дерево
        private void button1_Click(object sender, EventArgs e)
        {
            AvlTree NewTree = new AvlTree(); //создать объект типа дерева
 
            //вставка элементов
            string s = textBox1.Text;
            int[] x = StringToInt32Array(s);
            for (int i = 0; i < x.Length; i++)
            { NewTree.Insert(x[i]); }
            //***************
 
            label1.Text = NewTree.Printtree(); //распечатка дерева на экран
        }
 
//Кнопка, допустим - SAVE
        private void button2_Click(object sender, EventArgs e)
        {
            // serialise to file 
            using (var stream = File.Create("binary.bin"))
            {
                var formater = new BinaryFormatter();
                formater.Serialize(stream, treeNode);
            }
        }  
//Кнопка - LOAD
        private void button3_Click(object sender, EventArgs e)
        {
            // deserialise from file
            using (var stream = File.Open("binary.bin", FileMode.Open))
            {
                var formater = new BinaryFormatter();
                var tree = (TreeNode)formater.Deserialize(stream);
            }
        }
    }
}
0
taras atavin
4205 / 1768 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
15.04.2012, 09:37 13
Попробуй в дисковом варианте все связи между узлами представить смещениями от начала файла, а файл начать с заголовка, описывающего тип узла и хранящего по фиксированному для данного формата файла смещению смещение корня дерева. Например так: файл начинается со строки "Tree. Hex header. Rooot:", за которой следует в бинарной форме 64-х битное смещение корня, а за смещением cимвол перевода каретки и такая многострочная декларация:
"
C
1
2
3
4
5
6
struct node
{
int Data;
node *Left;
node *Right;
};
". Или другой вариант: xml-файл, потомки вкладываются тегами left/right в непосредственного предка:
"
XML
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?xml version="1.0" encoding="UTF-8"?>
<tree>
<root><data>4</data>
<left>
<data>2</data>
<left><data>1</data></left>
<right><data>3</data></right>
</left>
<right>
<data>6</data>
<left><data>5</data></left>
<right><data>7</data></right>
</right>
</root>
</tree>"
.
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
15.04.2012, 09:53  [ТС] 14
taras atavin, уф... пока это не мой уровень. Я не понял из того, что ты написал около 80%. Поэтому лучше сейчас добить что-то одно.. например сериализацию, понять основной начальный принцип. А потом уже углубляться. Я ведь с сохранением дело до сих пор не имел.
0
taras atavin
4205 / 1768 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
15.04.2012, 10:54 15
Как же ты тогда надеешься дерево хотя бы создать, если даже здесь не всё понятно? И уже тем более работать с ним? Лучше даже не "Hex header.", а "Hex XXXXXXXXXXXXXXXX header."
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
15.04.2012, 11:19  [ТС] 16
taras atavin, почитай посты повыше, пожалуйста. У меня дерево создается, обрабатывается, все нормально. Осталось только сохранить. А с сохранением объектов в с# я дело еще не имел, тем паче с сериализацией. - я об этом толкую. Тарас, помогать и объяснять - тоже великое искусство. Для меня
Цитата Сообщение от taras atavin Посмотреть сообщение
Лучше даже не "Hex header.", а "Hex XXXXXXXXXXXXXXXX header."
Это ни о чем не говорит, даже не знаю к чему относится... могу предположить, что к файлу xml. Но сейчас Константин помогает мне разобраться с классом BinaryFormatter. А этот класс создает двоичный (бинарный) файл.. а не xml. Так что вот....
0
Konctantin
940 / 744 / 171
Регистрация: 12.04.2009
Сообщений: 1,700
15.04.2012, 12:14 17
Чтобы не ругался компилятор подключите пространство имен
C#
1
System.IO;
далее. вы используете собственный класс, значит для него надо реализовать интерфейс ISerializable.

В общем вот, рабочий пример.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using System;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.Security.Permissions;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            AvlNode root = new AvlNode();
            root.Parent = new AvlNode() { Value = 1, Balance = 7, Parent = new AvlNode() { Value = 4, Balance = 7, } };
            root.Parent = new AvlNode() { Value = 2, Balance = 8, Parent = new AvlNode() { Value = 5, Balance = 8, } };
            root.Parent = new AvlNode() { Value = 3, Balance = 9, Parent = new AvlNode() { Value = 6, Balance = 9, } };
 
            Save(root);
 
            var tree = Load();            
        }
 
        static void Save(AvlNode node)
        {
            // serialise to file 
            using (var stream = File.Create("binary.bin"))
            {
                var formater = new BinaryFormatter();
                formater.Serialize(stream, node);
            }
        }
 
        static AvlNode Load()
        {
            // deserialise from file
            using (var stream = File.Open("binary.bin", FileMode.Open))
            {
                var formater = new BinaryFormatter();
                return (AvlNode)formater.Deserialize(stream);
            }
        }
    }
 
    [Serializable]
    public class AvlNode : ISerializable //структура узла дерева
    {
        public AvlNode Parent;
        public AvlNode Left;
        public AvlNode Right;
        public int Value;
        public int Balance;
 
        public AvlNode()
        {
        }
 
        protected AvlNode(SerializationInfo info, StreamingContext context)
        {
            if (info == null)
                throw new System.ArgumentNullException("info");
 
            Parent   = (AvlNode)info.GetValue("Parent",  typeof(AvlNode));
            Left     = (AvlNode)info.GetValue("Left",    typeof(AvlNode));
            Right    = (AvlNode)info.GetValue("Right",   typeof(AvlNode));
            Value    = (int)    info.GetValue("Value",   typeof(int));
            Balance  = (int)    info.GetValue("Balance", typeof(int));
        }
 
        [SecurityPermission(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            if (info == null)
                throw new System.ArgumentNullException("info");
 
            info.AddValue("Parent",  Parent);
            info.AddValue("Left",    Left);
            info.AddValue("Right",   Right);
            info.AddValue("Value",   Value);
            info.AddValue("Balance", Balance);
        }
    }
}
ЗЫ. И на будущее пользуйтесь поиском и справкой, там примеров более чем достаточно.
1
taras atavin
4205 / 1768 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
15.04.2012, 12:16 18
Цитата Сообщение от jjohndavis Посмотреть сообщение
Это ни о чем не говорит, даже не знаю к чему относится
К самому файлу.

Добавлено через 31 секунду
Цитата Сообщение от jjohndavis Посмотреть сообщение
предположить, что к файлу xml.
Нет. Это к бинарному.
0
Konctantin
940 / 744 / 171
Регистрация: 12.04.2009
Сообщений: 1,700
15.04.2012, 13:52 19
C#
1
public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
заменить на
C#
1
protected virtual void GetObjectData(SerializationInfo info, StreamingContext context)
не надо чтобы этот метод был доступен
0
jjohndavis
0 / 0 / 2
Регистрация: 10.10.2011
Сообщений: 16
15.04.2012, 19:59  [ТС] 20
Хочу выразить признательность Konctantin-у за неоценимую помощь! Все поехало и заработало! Также, всем спасибо, кто откликнулся! Буду осваивать сериализацию
0
15.04.2012, 19:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.04.2012, 19:59

Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя...

Как правильно сохранить и потом считать структуру в бинарный файл
Есть структура struct card { int size; char *lear; int *name; }; Эта...

Дозапись бинарного дерева в файл
Можете сказать алгоритм дозаписи бинарного дерева в файл и если не сложно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru