二叉树

Question

此计算垂直总和是我碰到其计算二叉树垂直和代码。由于该代码根本没有任何文档，我无法理解它是如何实际工作的，以及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); 
    } 
} 

Answer 1

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

取下面的树

    4 
      2   6 
     1  3  5  7 

的例子以下是节点的跨越纵线的分布

垂直线1 - 1
VERTI CAL 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; 
    } 

在这个循环中，你是计算从左边根最远点的距离（这不工作的时候，我们将讨论这个版本）。每次移动离开时，设备会通过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 i。e base = hd这就是当你的代码打印节点的值时