Здравствуйте,
читал тут Страуструпа. Он приводит пример структуры для хранения дерева. Никак не могу въехать, что хранится в её членах. Подскажите плиз.
Здравствуйте, potap, Вы писали:
P>Здравствуйте, P>читал тут Страуструпа. Он приводит пример структуры для хранения дерева. Никак не могу въехать, что хранится в её членах. Подскажите плиз.
P>
P>struct Tnode{
P> string word; // собственно хранимая величина. здесь: строка
P> int count; // возможно - количество узлов в этой ветви
P> Tnode * left; // левый дочерний узел
P> Tnode * right; // правый дочерний узел
P>}
P>
P>struct Tnode{
P> string word; // собственно хранимая величина. здесь: строка
ну это да, конечно
P> int count; // возможно - количество узлов в этой ветви
количество дочек ? или +внучек,правнучек и т.д.
P> Tnode * left; // левый дочерний узел
P> Tnode * right; // правый дочерний узел
т.е. дерево бинарное? Если да, то зачем count - число детей. Если нет - то как получить среднюю дочку?
Может, это вообще опечатка какая-нибудь? Это вообще-то в упражениях находится. Мне было бы понятно если дерево хранит словарь. о - отец для : он, ор, оса. он - отец для : они, оно, онуфрий. Но тогда бинарным деревом не обойтись ... :???:
P>}
P>
Здравствуйте, potap, Вы писали:
P>Здравствуйте, P>читал тут Страуструпа. Он приводит пример структуры для хранения дерева. Никак не могу въехать, что хранится в её членах. Подскажите плиз.
P>
Книги под рукой нет, так что не совсем ясно назначение поля count, а с остальными все более-менее понятно:
word — скорее всего хранимая величина
left — указатель на вершину левого поддерева
right — указатель на вершину правого поддерева
count — возможно общее число потомков
Здравствуйте, potap, Вы писали:
P>Здравствуйте, Кодт, Вы писали:
P>>
P>>struct Tnode{
P>> string word; // собственно хранимая величина. здесь: строка
P>//ну это да, конечно
P>> int count; // возможно - количество узлов в этой ветви
P>//количество дочек ? или +внучек,правнучек и т.д.
P>> Tnode * left; // левый дочерний узел
P>> Tnode * right; // правый дочерний узел
P>//т.е. дерево бинарное? Если да, то зачем count - число детей.
P>// Если нет - то как получить среднюю дочку?
P>>}
P>>
count — это количество дочек+внучек+...
Потому что просто количество дочек считается как (left!=0) + (right!=0)
Нужно, к примеру, для балансирования дерева.
P>Может, это вообще опечатка какая-нибудь? Это вообще-то в упражениях находится.
Задача подсчета количества узлов в ветви — вполне "упражнятельная".
P>Мне было бы понятно если дерево хранит словарь. о — отец для : он, ор, оса. он — отец для : они, оно, онуфрий. Но тогда бинарным деревом не обойтись ...
Ну ты сам предложил тернарное дерево. А почему нельзя бинарное?
Бинарное Б-дерево.
о +
+-> он +
| +-> они
| +-> оно
|
+-> онуфрий +
+-> ор
+-> оса
Дерево сравнений:
+-> о
+-> он +
| +-> они
оно +
| +-> онуфрий
+-> ор +
+-> оса
Здравствуйте, Кодт, Вы писали:
К>Потому что просто количество дочек считается как (left!=0) + (right!=0)
К>Нужно, к примеру, для балансирования дерева.
это как ? что значит "балансирование дерева" ?
P>Мне было бы понятно если дерево хранит словарь. о — отец для : он, ор, оса. он — отец для : они, оно, онуфрий. Но тогда бинарным деревом не обойтись ...
К>Ну ты сам предложил тернарное дерево.
Я чисто для примера предложил. Случайно оказалось, что дочек у всех по три. Пусть будет ещё "она" и у "он" будет уже 4 дочки.
А почему нельзя бинарное?
К>Бинарное Б-дерево.
Да нет. "онуфрий" дочка для "он", а не "о". "он" лучше подходит на роль отца.
Я имел ввиду такое дерево :
о +
+-> он +
| +-> они
| +-> оно
| +-> онуфрий
| +-> она
|
+-> ор +
+-> оса+
Здравствуйте, potap, Вы писали:
К>>Нужно, к примеру, для балансирования дерева.
P>это как ? что значит "балансирование дерева" ?
Балансированное дерево — такое, что в каждой дочерней ветке поровну (почти поровну) узлов.
Балансирование — перестройка дерева так, чтобы оно стало балансированным.
P>>Мне было бы понятно если дерево хранит словарь. о — отец для : он, ор, оса. он — отец для : они, оно, онуфрий. Но тогда бинарным деревом не обойтись ...
К>>Ну ты сам предложил тернарное дерево. P>Я чисто для примера предложил. Случайно оказалось, что дочек у всех по три. Пусть будет ещё "она" и у "он" будет уже 4 дочки.
К>>А почему нельзя бинарное?
К>>Бинарное Б-дерево. P>Да нет. "онуфрий" дочка для "он", а не "о". "он" лучше подходит на роль отца. P>Я имел ввиду такое дерево : P>
P>о +
P> +-> он +
P> | +-> они
P> | +-> оно
P> | +-> онуфрий
P> | +-> она
P> |
P> +-> ор +
P> +-> оса+
P>
Это еще одна разновидность: дерево с неограниченным (или равным алфавиту) числом дочерних узлов.
Словарю в принципе по барабану, в какой структуре храниться.
Можно в твоей (каждый уровень — другая буква),
можно в Б-дереве ( узел < дочка1 < правнучка1 < дочка2 ... < правнучкаN < следующий )
можно в дереве сравнений ( дочка1 < правнучка12...2 < узел < правнучка21...1 < дочка2 )
При этом слова, начинающиеся, скажем, на "он" с легкостью находятся во всех структурах.
Быстрее всего — в алфавитном дереве, затем — в Б-дереве, затем — в дереве сравнений.
Здравствуйте, potap, Вы писали:
P>Здравствуйте, P>читал тут Страуструпа. Он приводит пример структуры для хранения дерева. Никак не могу въехать, что хранится в её членах. Подскажите плиз.
Два поля данных, связанных с узлом дерева и две ссылки: на левого и правого потомков
Могу предположить, что описанная структура используется в задаче, где нужно вывести количество повторений для каждого слова в некотором тексте, тогда
word — слово,
count — количество повторений word в исходном тексте.
Перекуём баги на фичи!
