二叉樹遞歸removeLeftmost（）方法是如何工作的？

Question

該方法的規範聲稱，該方法從根開始將移除最左邊的節點並修復樹結構。它還說，如果最左邊的節點沒有左子節點將左子節點的父節點（可能爲空）附加到最左節點的父節點（我沒有看到在代碼中發生了什麼）。這裏是代碼：

public BTNode removeLeftmost() 
{ 
    if(left == null) 
     return right; 
    left = left.removeLeftmost(); 
    return this; 
} 

我只是沒有看到它是如何返回整個樹與最左邊的節點返回。主要是第一部分讓我很困惑，如果它返回正確的孩子，如果留下== == null。如果我深入樹（由於遞歸調用），不會返回右邊砍掉很多樹？

Answer 1

下面是它的辦案：

  9 
     /\ 
     8 12 
    /\ 
     5 20 
     \ 
     6 
     \ 
      7 

當我們到達5，它的最左邊的節點（left == null）。我們需要刪除它。所以5權（即6）返回給調用者（return right;），並且調用者使6的8（left = left.removeLeftmost()）新左樹..

  9 
     /\ 
     8 12 
    /\ 
     6 20 
     \ 
     7 

然後8被返回給調用者（return this ）並被指定爲9（left = left.removeLeftmost()）的左節點。但8已經是9的左邊孩子，所以這不會改變任何東西。

Answer 2

我假設這是一個二叉搜索樹，否則你不需要修復結構，正確嗎？

它所做的是沿着樹移動，直到沒有更多的分支到左邊，即只關於左邊，你已經到了葉。

if (left !=null){ left = left.removeLeftmost(); }

在這一點上，移植物對兒童有權到父那裏左樹是現場分支（由left = left.removeLeftmost();再次），然後將返回以前的分支在同一個地方一直回到樹的根部。