3
Возможно ли, что узел в полном двоичном дереве имеет только один ребенок? спасибоо полном двоичном дереве
Это может быть полное двоичное дерево?
23
/\
12 15
/\
9 11
/\ \
10 5 13
A
ответ
6
ОК, прежде всего, чтобы сделать разницу между идеальным и полным двоичным деревом. В идеальном бинарном дереве каждый узел имеет двух детей (если не лист) или нет детей (если лист). Таким образом, идеальное двоичное дерево уровня N имеет полностью 2^(N + 1) - 1 узлов. Но если мы говорим о полном двоичном дереве - это означает, что каждый уровень, кроме последнего, заполнен, а последний уровень может быть не полным. Также в полном двоичном дереве последние узлы уровня должны быть заполнены слева направо.
Так что если вы говорите о идеальном двоичном дереве, это невозможно. Но если вы имеете в виду полное двоичное дерево, возможно иметь только одного ребенка.
0
Цитируя Википедии:
Полное бинарное дерево бинарное дерево, в котором каждый уровень, кроме , возможно, наконец, полностью заполнены, и все узлы в крайнее левое положение , насколько это возможно.
Это означает, что нет.
+2
«за исключением ...», за которым следует «нет», является нелогичным, то есть логическим ошибочным. –
+0
Не должно быть «Что значит« да »? –
+0
Что означает «нет» => предоставленный пример не является полным двоичным деревом. – vlood
3
Я бы сказал, что это возможно:
*
/\
/ \
* x
/\ /
* * *
это
бинарное дерево, в котором каждый уровень, за исключением, возможно, последний, полностью заполнен, и все узлы являются как можно дальше
И узел x h как только один ребенок.
+0
Зависит от определения, и я хотел бы иметь источник для вас, но да, это * - это разумное определение, которое позволяет это. +1 –
+0
Я взял определение из ответа vlood. – phimuemue
0
Из других ответов:
Полное бинарное дерево представляет собой бинарное дерево, в котором каждый уровень, за исключением, возможно, последний, полностью заполнен, и все узлы, как далеко влево, насколько это возможно.
23
/\
12 15
/\
9 11 <- not the last level, but not completely filled!
/\ \
10 5 13 <- last level: not completely filled, but that's okay
Так что этот пример дерева не является полным, в соответствии с этим определением.
Это домашнее задание? Пожалуйста, отметьте это [домашнее задание]. –
НЕТ, это не домашняя работа – user355002
Нет, это не полное двоичное дерево. Узлы должны быть выровнены слева направо. Если 13-й узел был левым дочерним, а не справа, ваше двоичное дерево будет завершено. –