我如何找到每个节点的高度并在二叉搜索树中为其分配后序？

Question

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

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)
{


}```

Answer 1

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

尽管您的问题标题提到“post-order”（与递归相关的术语），但您的代码实际上并不是递归的。通常，post-order 更新发生在递归调用之后。

无论如何，使用您的迭代解决方案，高度仍然可以轻松更新，因为您已经在树节点中存储了 parent 指针。因此，您需要做的就是返回每个节点并更新高度。

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;
    }
}

需要注意的是你的tree heights好像是把一个叶子节点的高度（也就是没有children的节点的高度）当成0。为了让你的fix_height函数well-behaved即使在叶子节点上调用，那么“没有child”的高度也被当成-1.

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

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

我如何找到每个节点的高度并在二叉搜索树中为其分配后序？

How would I find the height of each node and assign it postorder in a binary search tree?

c++

binary-search-tree

nodes