Как проверить, завершено ли двоичное дерево в Java - PullRequest
Новая
       10

Как проверить, завершено ли двоичное дерево в Java

1 голос
/ 06 мая 2011

У меня много проблем с этой задачей.Используя определение Википедии для полного двоичного дерева:

Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы расположены как можно левее.

Мне нужен способ проверки этих условий, но, как бы я ни старался, я ничего не могу придумать.Если бы я должен был передать вход TreeNode tree в метод checkComplete, как я мог бы пройти через двоичное дерево и проверить, что оно завершено?Может кто-нибудь помочь с псевдокодом или объяснение того, как это возможно?Здесь был еще один вопрос: Как определить, является ли двоичное дерево полным?

В этом ответе был псевдокод, но я не мог понять, где были все случайные величиныисходя из того, что они должны были представлять, или почему в последних 3 строках было два значения в скобках.Если бы кто-то мог помочь с другим представлением, я был бы очень признателен.

Спасибо.

Ответы [ 2 ]

2 голосов
/ 05 сентября 2012 
int CT()
{
  int lh=0, rh=0, sign=1;
  if (!root->left && !root->right) 
    return 1;
  if (!root->left && root->right) 
    return 0;

  lh = CT(root->left);
  rh = CT(root->right);

  if (lh == 0 || rh == 0) 
    return 0;
  if (lh < 0 && rh < 0) 
    return 0;
  if (lh < 0 || rh < 0) 
    sign = -1;
  if (|lh| == |rh| ) 
    return (|lh|+1)*sign;
  elseif (rh == lh-1) 
    return -(|lh|+1);
  else return 0;
}

if CT returns '0' - its not a complete tree.
'-' is used to check mismatch in height is encountered on one subtree only.
1 голос
/ 06 мая 2011

Пройдите по дереву слева направо.Есть несколько критических точек, в которых вы хотите сохранить или сравнить информацию:

  • Когда вы нажимаете на первый листовой узел.
  • Когда вы нажимаете на следующие листовые узлы.
  • Когда вы попадаете на первый листовой узел на другом расстоянии от корня.

Поскольку это домашнее задание, вам, вероятно, следует взять его до конца от этой подсказки.

...