1

这是我遇到的一个代码，它计算二叉树中的垂直和。由于代码根本没有任何文档，我无法理解它实际上是如何工作的，以及 if(base==hd) 的条件到底是什么？需要帮助 ：）

 void vertical_line(int base,int hd,struct node * node)
{
    if(!node) return;
    vertical_line(base-1,hd,node->left);
    if(base==hd) cout<<node->data<<" ";    
    vertical_line(base+1,hd,node->right);
}
void vertical_sum(struct node * node)
{
    int l=0,r=0;
    struct node * temp=node;
    while(temp->left){
        --l;temp=temp->left;
    }
    temp=node;
    while(temp->right){
    ++r;temp=temp->right;
    }
    for(int i=l;i<=r;i++)
    {
        cout<<endl<<"VERTICAL LINE "<<i-l+1<<" : ";
        vertical_line(0,i,node);
    }
}
4

1 回答 1

1

它试图以垂直顺序显示树 - 让我们尝试了解什么是垂直顺序

以下面的树为例

                  4
            2           6
         1     3     5     7

以下是节点在垂直线上的分布

垂直线 1 - 1
垂直线 2 - 2
垂直线 3 - 3,4,5
垂直线 4 - 6
垂直线 5 - 7

我们如何确定 3,4,5 是垂直线 3 的一部分。我们需要找到节点到根的水平距离来确定它们是否属于同一条线。我们从水平距离为零的根开始。如果我们向左移动，则需要将父节点的距离减 1，如果向右移动，则需要将父节点的距离增加 1。同样适用于树中的每个节点，即如果父节点的水平距离为 d，则左孩子的距离是d-1，右孩子的距离是d+1

在这种情况下，节点 4 的距离为 0。节点 2 是 4 的左子节点，因此它的距离为 -1（减 1）。节点 6 是 4 的右孩子，所以它的距离是 1（增加 1）。

节点 2 的距离为 -1。节点 3 是 2 的右子节点，因此它的距离为 0（以 1 为增量）同样适用于节点 5。节点 3、4、5 的水平距离为零，因此它们落在同一条垂直线上

现在来到你的代码

while(temp->left){
        --l;temp=temp->left;
    }

在这个循环中，您正在计算左侧距根最远节点的距离（这并不总是有效，我们将在稍后讨论）。每次向左移动时，l 的值都会减 1。

while(temp->right){
    ++r;temp=temp->right;
    }

使用与上述类似的逻辑，您是计算右侧距根最远节点的距离

现在您知道左侧和右侧的最远距离，您正在垂直显示节点

 for(int i=l;i<=r;i++)
    {
        cout<<endl<<"VERTICAL LINE "<<i-l+1<<" : ";
        vertical_line(0,i,node);
    }

上述循环中的每次迭代都会在垂直线上显示节点。（这不是有效的）。您正在为每一行调用 vertical_line 方法

void vertical_line(int base,int hd,struct node * node)
{
    if(!node) return;
    vertical_line(base-1,hd,node->left);
    if(base==hd) cout<<node->data<<" ";    
    vertical_line(base+1,hd,node->right);
}

上述方法将打印落在 hd 线上的节点。该方法遍历整个树，计算每个节点的距离，即基数包含节点的水平距离值。如果节点是垂直线 hd 的一部分，则 base 等于 hd 即 base = hd，这是您的代码打印节点值的时候

于 2013-10-16T14:17:57.597 回答