В заданном двоичном дереве подсчитайте число элементов в 2 раза больших минимального элемента

@vitalionchik · Регистрация: 14.03.2018

Author24 — интернет-сервис помощи студентам

В заданном двоичном дереве подсчитайте число элементов в 2 раза больших минимального элемента.

@JuriiMW · 25.04.2018, 06:35

Pascal

type
  tTree = class
    N : Integer;
    L, R : tTree;
  end;
  
function minInTree(Tree : tTree) : Integer := Tree.L = nil ? N : minInTree(Tree.L);
 
function moreVal(Tree : tTree; val : Integer) : Integer := (N > val ? 1 : 0) + (L <> nil ? moreVal(Tree.L, val) : 0) + (R <> nil ? moreVal(Tree.R, val) : 0);
 
function find2moreMin(Tree : tTree) := moreVal(Tree, minInTree(Tree) * 2);

Функция find2moreMin(root) вернёт нужный результат.

P.S. Двоичное дерево обычно заполняется так, что его минимум находится в самой нижней левой ветке.

P.P.S. Обход дерева можно сократить:

Pascal

9	function moreVal(Tree : tTree; val : Integer) : Integer := (N > val ? 1 + (L <> nil ? moreVal(Tree.L, val) : 0) : 0) + (R <> nil ? moreVal(Tree.R, val) : 0);

@volvo · 25.04.2018, 12:09

Сообщение от JuriiMW

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

Ничего подобного. Это двоичное дерево поиска так заполняется. А двоичное дерево в общем виде - неупорядочено.

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

@vitalionchik 0 / 0 / 0 Регистрация: 14.03.2018 Сообщений: 49
		1
	В заданном двоичном дереве подсчитайте число элементов в 2 раза больших минимального элемента 24.04.2018, 17:52. Показов 958. Ответов 2 Метки нет (Все метки) В заданном двоичном дереве подсчитайте число элементов в 2 раза больших минимального элемента. 0

@volvo Супер-модератор 32830 / 21168 / 8147 Регистрация: 22.10.2011 Сообщений: 36,428 Записей в блоге: 8
	25.04.2018, 12:09	3
	Сообщение от JuriiMW Двоичное дерево обычно заполняется так, что его минимум находится в самой нижней левой ветке. Ничего подобного. Это двоичное дерево `поиска` так заполняется. А двоичное дерево в общем виде - неупорядочено. А если это двоичное дерево поиска - то достаточно найти первый элемент, в два раза больший, чем минимум и пройти по его правым потомкам, пока значение узла не изменится. 0

Опции темы

В заданном двоичном дереве подсчитайте число элементов в 2 раза больших минимального элемента

Решение