c++ - 我如何找到每个节点的高度并在 binary search tree 中为其分配后序?

我有一个带有高度属性的附加节点类的模板类。我希望能够在插入新节点后验证每个节点的高度。我的插入节点功能运行良好,我只是对插入新节点后如何更改每个节点的高度感到困惑。

template <typename T>
class BST
{
public:
    class Node 
    {
    public:
        T key;
        int height = 0;    
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
       
        Node(){}
       
        Node(T k, Node* input_node = nullptr)
        {
            key = k;
            parent = input_node;
        }
    };

private:
   
    Node* root_ = nullptr;
    unsigned int size_ = 0;

public:

   BST(); 

   ~BST();

   void insert(T k);

private: 

    void fix_height(Node* node);


template <typename T>
void BST<T>::insert(T k)
{
    
    Node* node = root_; // insert function 
    Node* prev_node = node;
    bool went_right;

    if(node == nullptr)
    {
        root_ = new Node(k);
        ++size_;
        return;
    }
    while(node != nullptr)
    {
        prev_node = node;
        if(k < node->key)
        {
            node = node->left;
            went_right = false;
        }
        else if (k > node->key)
        {
            node = node->right;
            went_right = true;
        }
        
        else
        {
            return;
        }
    }
    
    if(went_right)
    {
        prev_node->right= new Node(k, prev_node); // assigning the new node 
    }
    else
    {
        prev_node->left= new Node(k, prev_node);
    }
    ++size_;

    
    
}

template <typename T> 
void BST<T>::fix_height(Node* node)
{


}```

回答1

节点的高度定义为其子 nodes 高度的最大值加 1。

尽管您的问题标题提到了“后序”(与递归相关的术语),但您的代码实际上并不是递归的。通常,订单后更新发生在递归调用之后。

无论如何,通过您的迭代解决方案,高度仍然可以轻松更新,因为您已将父指针存储在树 nodes 中。因此,您需要做的就是返回每个节点并更新高度。

template <typename T> 
void BST<T>::fix_height(Node* node)
{
    while (node)
    {
        node->height = 1 + std::max(
            node->left ? node->left->height : -1,
            node->right ? node->right->height : -1);
        node = node->parent;
    }
}

应该注意的是,您的树高度似乎将叶节点的高度(即没有子节点的节点的高度)视为 0。为了使您的 fix_height 函数即使在叶上调用也表现良好节点,则“无子”的高度被视为-1。

如果您决定叶节点的高度实际上应该为 1,那么您应该将那些“无子”高度更改为 0,并将新节点的默认高度更改为 1。

要使用它,您将在从 insert 函数返回之前调用 fix_height(prev_node);

相似文章

java - 在二叉搜索树中实现 nodeCount() 和 leafCount()

我正在尝试为这个递归二叉树程序实现leafCount()和nodeCount()。在测试它时,这两种方法(或它们的测试)会抛出失败,所以很明显它们没有按预期工作。我无法弄清楚我在哪里做错或想错了。如果...