二叉樹

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這就是當你的代碼打印節點的值時