什麼是二進制子樹的最左邊和最右邊的節點？

最右邊的節點將在左子樹，我認爲那時，最左邊的是右子樹的最大價值最大價值的節點。

然而，在another article它讓我看到了不同的方法來找到最左邊的節點：

1）如果給定節點沒有右孩子：

跳轉到指定節點的根，直到它任何節點的左側子節點。該節點將成爲樹中的下一個較高節點。

2）如果給定節點具有右子：

a）如果給定節點的右孩子沒有左孩子

The right child will be the next higher node.

b）如果給定節點的右子有左子

The leftmost leaf node will be the next higher node.

即第2個方法不返回最大的價值是1方法建議請澄清..

來源

2015-11-01 Square-root

根據你附加的鏈接判斷，我假設你正在專門討論二元搜索樹，它們有關於它們節點構成的規則。

至於二叉樹一般規則（通過擴展，子樹）：

每個孩子的節點的右側會比節點更大。
節點左側的每個小孩都會比節點小。

因此，任何給定子樹的最右邊的孩子總是最高的值。而且，任何給定子樹的最左邊的孩子總是最低的值。

請記住，二叉樹與二叉搜索樹略有不同，並且這些規則不一定適用於二叉樹。

讓我們用下面的二叉搜索樹爲例：

假設我們正在試圖尋找樹的最高節點值。如果我們從節點9開始（「根」），我們繼續向下遍歷節點的每個右側子節點，直到沒有更多的右側子節點（即，從節點9開始，然後向下移動到節點13，然後結束節點16）。因此，16是樹中最高的值。

類似地，在樹中搜索最低節點值時，我們從樹的根節點開始，繼續遍歷每個左邊的孩子，直到沒有更多的左邊孩子存在。

來源：大學（IT學生）在我的數據結構和算法課程中所學這個

希望這會有所幫助，請隨時糾正我可能犯任何錯誤（我是新來的）。

來源

2015-11-01 04:25:48 user3341765

這個想法是使用Level Order Traversal。要找到第一個節點，我們使用一個變量isFirst。爲了分離等級，我們在每個關卡後排隊NULL。因此，在層次順序遍歷中，如果我們看到NULL，我們知道下一個節點將成爲其級別的第一個節點，因此我們設置isFirst。

void printCorner(Node *root) 
{ 
    queue<Node *> q; 
    q.push(root); 
    q.push(NULL); 
    bool isFirst=false; 
    bool isOne = false; 
    int last; 
    Node *temp; 
    while(!q.empty()){ 
     temp = q.front(); 
     q.pop(); 
     if(isFirst){ 
      cout<<temp->key<<" "; 
      if(temp->left)q.push(temp->left); 
      if(temp->right)q.push(temp->right); 
      isFirst = false; 
      isOne = true; 
     } 
     else if(temp==NULL){ 
      if(q.size()>=1)q.push(NULL); 
      isFirst = true; 
      if(!isOne)cout<<last<<" "; 
     } 
     else{ 
      last = temp->key; 
      isOne = false; 
      if(temp->left)q.push(temp->left); 
      if(temp->right)q.push(temp->right); 
     } 
    } 
}

來源

2017-12-24 15:05:03 HeadAndTail

什麼是二進制子樹的最左邊和最右邊的節點？

回答

相關問題