找到最大高度的平衡BST [英] Find balanced BST with max height

问题描述

大家好！



我想找到一种方法来搜索BST的最大高度平衡子树。



我尝试了什么：



我到目前为止能够找到检查高度的方法一棵树，检查树是否平衡。我很难让这些工作找到最大高度的BST。



根据KarstenK的提示，我修改了我的代码以包含指针：< br $> b $ b

Hello all!

I am trying to figure out a way to search a BST for its balanced subtree with max height.

What I have tried:

I have so far been able to find methods to check the height of a tree and to check whether the tree is balanced. I'm having a hard time getting these to work to locate the BST with max height.

As per KarstenK's hint, I have modified my code to include pointers:

typedef struct Tree {
    int key;
    struct Tree *left;
    struct Tree *right;
} Tree;

int max(int a, int b)
{
    if (a >= b)
        return a;
    else
        return b;
}

int height(Tree* t)
{
    if (t == NULL)
        return 0;
    return 1 + max(height(t->left), height(t->right));
}

int IsBalanced(Tree *t)
{
    int lheight;
    int rheight;

    if (t == NULL)
        return 1;

    lheight = height(t->left);
    rheight = height(t->right);

    if (abs(lheight-rheight) <= 1 &&
        IsBalanced(t->left) &&
        IsBalanced(t->right))
        return 1;

    return 0;
}

以上似乎工作正常。然而，以下获得最大高度BST的镜头失败：

The above seems to work fine. However, the following shot at getting the max-height BST fails:

void MaxBalanced(Tree *t, Tree *maxBal, int *maxBal_height)
{
    int t_height;

    if (t == NULL)
        *maxBal_height += 0;

    if (IsBalanced(t) == 1){
        t_height = height(t);
        if (t_height >= *maxBal_height){
            maxBal = t;
            *maxBal_height = t_height;
        }
    }
    else{
        MaxBalanced(t->left, maxBal, maxBal_height);
        MaxBalanced(t->right, maxBal, maxBal_height);
    }
}

int main()
{
    int i;

    Tree* t = NULL;

    int j[20] = { 993, 591, 2, 4, 395, 97, 446, 38, 279, 587, 28, 50, 265, 502, 114, 493, 808, 716, 897, 987 };

    for (i = 0; i < 20; i++)
        t = InsertBST(t, j[i]);

    DisplayTree(t);

    Tree* maxBal = NULL;
    int maxBal_height = 0;
    MaxBalanced(t, maxBal, &maxBal_height);

    DisplayTree(maxBal);

    return 0;
}

DisplayTree是一个（相当长的）函数，用于以图形方式显示树。代码运行没有错误，但是，我得到一个空树。我将不胜感激。

DisplayTree is a (rather long) function to present the tree graphically. The code runs without errors, however, I get an empty tree. I would appreciate any comments.

推荐答案

要获得最大高度，您需要将实际最大值存储在某处并将其与实际值进行比较。



而且你缺少一些边缘情况，比如MaxBalanced中的最后一个缺少的东西。



你需要一个非后备平衡树。

To get the maximum height you need to store your actual maximum somewhere and compare it with the actual value.

And your are missing some edge cases like the last else in MaxBalanced which is missing.

You need a fallback in non-balanced trees.

这篇关于找到最大高度的平衡BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！