No Image

Узел дерева который не имеет предков

СОДЕРЖАНИЕ
1 218 просмотров
10 марта 2020

Чтобы добавить хороший ответ необходимо:

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

Этого делать не стоит:

  • Копировать ответы со сторонних ресурсов. Хорошо ценятся уникальные и личные объяснения;
  • Отвечать не по сути: «Подумай сам(а)», «Легкотня», «Не знаю» и так далее;
  • Использовать мат – это неуважительно по отношению к пользователям;
  • Писать в ВЕРХНЕМ РЕГИСТРЕ.
Есть сомнения?

Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.

Трудности с домашними заданиями? Не стесняйтесь попросить о помощи – смело задавайте вопросы!

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

Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными.

Содержание

Определения [ править | править код ]

  • Корневой узел — самый верхний узел дерева (узел 8 на примере).
  • Корень — одна из вершин, по желанию наблюдателя.
  • лист, листовой или терминальныйузел — узел, не имеющий дочерних элементов (узлы 1, 4, 7, 13).
  • Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом (3, 6, 10, 14).

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

  • Полный сцепленный ключ — идентификатор записи, который образуется путём конкатенации всех ключей экземпляров родительских записей (групп).
Читайте также:  Яндекс маркет оставить отзыв связной

Узлы [ править | править код ]

Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья ‘растут’ вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.

Корневые узлы [ править | править код ]

Узел, не имеющий предков (самый верхний), называется корневым узлом. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.

Поддеревья [ править | править код ]

Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).

Читайте также:  Getelementbyid style display none

Упорядочивание деревьев [ править | править код ]

Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.

Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.

Представление деревьев [ править | править код ]

Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).

Деревья как графы [ править | править код ]

В теории графов дерево — связный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения «родитель-потомок». Несвязный граф, состоящий исключительно из деревьев, называется лесом.

Методы обхода [ править | править код ]

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков, называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Читайте также:  Автоматическая очистка оперативной памяти компьютера windows 7

Список вопросов теста

Вопрос 1

Что такое дерево?

Варианты ответов
  • Связный граф, не содержащий циклов
  • Неориентированный граф без петель и кратных ребер
  • Ориентированный граф без циклов
  • Граф, у которого могут быть ориентированные и неориентированные ребра
Вопрос 2

Узел дерева, который не имеет предков, называется…

Варианты ответов
  • сыном
  • листом
  • корнем
  • промежуточным узлом
Вопрос 3

Как называются предки узла, имеющие уровень на единицу меньше уровня этого узла?

Варианты ответов
  • детьми
  • родителями
  • братьями
  • сестрами
Вопрос 4

Укажите, сколько вершин — непосредственных потомков может иметь вершина произвольного дерева?

Варианты ответов
  • Любое количество
  • Две
  • Не более двух
  • Не менее одной
Вопрос 5

Узел, не имеющий потомков?

Варианты ответов
  • Корень
  • Лист
  • Предок
  • Родитель
Вопрос 6

Как называется дерево, в котором каждый узел может иметь не более двух сыновей?

Варианты ответов
  • Ориентированное
  • Бинарное
  • Неориентированное
  • Корневое
Вопрос 7

Сколько ребер в дереве с пятью вершинами?

Варианты ответов
  • 4
  • 5
  • 6
  • 7
Вопрос 8

Высотой дерева называется…

Варианты ответов
  • максимальное количество листьев
  • максимальное количество связей
  • максимальная длина пути от корня до листа
  • максимальное количество узл
Вопрос 9

Глубиной вершины называется…

Варианты ответов
  • длина пути в этой вершины в корень
  • максимальная длина пути от корня до листа
  • максимальное количество узлов
  • длина пути в эту вершину из корня
Вопрос 10

Пусть граф G с n вершинами является деревом.

Выберите для G НЕверное утверждение

Комментировать
1 218 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock
detector