平衡二叉树编码

Question

嘿，伙计们，我刚刚开始在我的课程中学习二叉树，最近有人问我这个问题。多亏了我令人难以置信的糟糕的实现和对问题的充分理解，我根本不知道如何解决这个问题。请帮帮我！

有n个结点的二叉树T称为h-平衡的，如果对于T中的任何结点u，它的两个子树的高度之差至多为h，其中h >= 0是一个整数。假设一棵空树的高度为-1。假设每个节点u有三个字段: u.lc指向u的左子节点，如果没有左子节点，则u.lc = NULL；u.rc指向u的右子节点，如果没有右子节点，则u.rc = NULL；u.height应设置为以u为根的树的高度。

(a)给定指向树根的r，用伪代码(或C/C++)设计一个算法，填充u:height中每个节点u的高度。

(b)假设每个节点的高度u存储在u.height中，编写一个算法来检查T是否h平衡。(提示:修改(A)中设计的算法)

Answer 1

这甚至不是伪代码，但在此过程中应该会对您有所帮助。

如果你更正式地陈述一个问题的条件，它通常会让问题变得更清楚：

a)

• 叶子的高度是-1\f25
• -1\f6内部节点的高度比它的两个子树的最大高度大1。

b)

• 一个叶子是h平衡的，一个内部节点是h平衡的当且仅当它的两个子树都是h平衡的，并且它们的高度之差至多是h。

正如您所看到的，这两个问题遵循相同的模式:一个是叶子情况，另一个是依赖于两个子树的情况。

这是二叉树上递归的一般形式：

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
}