Баланс Двоичное дерево Кодирование

Question

Эй, ребята, я только начал изучать бинарное дерево в своем курсе, и меня недавно задали этот вопрос. Благодаря моей невероятно плохой реализации и недостаточному пониманию того, что задает вопрос, я просто не знаю, как это решить. Пожалуйста, помогите мне!!!

Бинарное дерево Т с п узлами называется ч-баланса, если для любого узла у в Т, разность высот двух суб-деревьев в большинстве Н, где Н> = 0 является целое число. Предположим, что пустое дерево имеет высоту -1. Предположим, что каждый узел u имеет три поля: u.lc указывает на левый дочерний элемент u и u.lc = NULL, если u не имеет левого ребенка; u.rc указывает на правильный дочерний элемент u и u.rc = NULL, если u не имеет правильного ребенка; u.height должен быть установлен как высота дерева, укорененного в u.

(a) При задании r, указывающего на корень дерева, создайте алгоритм в псевдокоде (или C/C++), который заполняет высоту каждого узла u в u: height.

(b) Предположим, что высота каждого узла u хранится в u.height, напишите алгоритм , проверьте, является ли T сбалансированным. (Подсказка: измените алгоритм, разработанный в (a))

Answer 1

Это даже не псевдокод, но должен помочь вам немного по пути.

Это часто делает проблему более понятной, если вы заявляете свои условия более формально:

)

• Высота листа составляет -1
• Высота внутреннего узла один больше чем максимум высот его двух поддеревьев.

б)

• Лист представляет собой Н сбалансированные
• Внутренний узел ч сбалансирована тогда и только тогда, когда оба его поддерева ч сбалансированы и разность их высот составляет не более час

Как вы можете видеть, обе проблемы следуют одному и тому же шаблону: один лист и случай, который зависит от двух поддеревьев.

Это общая форма рекурсии на бинарных деревьев:

void recurse(t) 
{ 
    if (t is a leaf, i.e. an empty tree) 
    { 
     handle the leaf case 
    } 
    else 
    { 
     do something that depends on 
      recurse(left subtree of t) 
     and 
      recurse(right subtree of t) 
    } 
} 

Я оставляю остальную часть решения в качестве упражнения.

Answer 2

Вот алгоритм. Предположим, что структура узла объявляется следующим образом:

struct Node { 
    Node *l; // left child 
    Node *r; // right child 
    int h; // subtree height 
}; 

Затем

void CalcHeights(Node *n) 
{ 
    if(n != NULL) 
    { 
     CalcHeights(n->l); // calc height in subtrees 
     CalcHeights(n->r); 
     int hl = n->l ? n->l->h : -1; // read calculated heights 
     int hr = n->r ? n->r->h : -1; 

     n->h = (hl > hr ? hl : hr) + 1; // get the bigger one plus 1 
    } 
} 

bool TestBalanced(Node const *n, int h) 
{ 
    if(n != NULL) 
    { 
     if(! TestBalanced(n->l, h) || ! TestBalanced(n->r, h)) 
      return false;    // unbalanced subtree... 

     int hl = n->l ? n->l->h : -1; // get subtrees heights 
     int hr = n->r ? n->r->h : -1; 

     return abs(hl - hr) <= h; // test the difference against H 
    } 
    return true; // empty tree is balanced 
}