如何動態地重新定位二叉樹節點

我一直在使用下面的代碼：http://bl.ocks.org/NPashaP/7683252。這是一棵樹的圖形表示。我剝去了大部分代碼（優雅標籤），每個父代只允許兩個節點，並將數據結構更改爲一個數組。如何動態地重新定位二叉樹節點

現在剩下的唯一問題是重新定位。原始代碼完美無缺。但是因爲我想要一個二叉樹，所以我讓用戶選擇插入一個左側或右側的孩子。原始的重新定位代碼將第一個孩子直接從父代中移除，但是在二叉樹中這是錯誤的。我希望它能夠左轉或右轉。

reposition = function (v) { 
    function repos(v) { 
     var lC = getLeafCount(v.v), 
      left = v.p.x; //parent's x-position 

     v.c.forEach(function (d) { 
      var vc = d; //saving reference of the child in parent object 
      d = tree.getVerticeById(d.v); //actually fetching the child object 
      var w = 0; 
      if(d.d == 'right') { w += 15 * lC } 
      if(d.d == 'left') { w -= 15 * lC } 
      d.p = {x: left + w, y: v.p.y + tree.h}; //setting the position 
      vc.p = d.p; //setting the child's pos in parent obj 
      repos(d); 
     }); 
    } 
    repos(v[0]); 
};

我的代碼的一些部分與原始代碼不同，因爲我已經改變了前面所述的數據結構。我試圖評論可能令人困惑的部分，但重要的是重新定位的數學。

起初，這段代碼看起來效果不錯（https://i.stack.imgur.com/gjzOq.png）。但經過一些測試後，我發現重新定位存在一個巨大的問題：節點彼此崩潰（https://i.stack.imgur.com/pdQfy.png）！

結論：我試圖修改原始功能，以記住節點的左右位置，但無法做到這一點。我寫了這種方法的變體，但它仍然有一些問題，如圖片中所示。我會感謝在這個問題上的一些意見。

來源

2017-04-07 Daniel

我最終爲此問題做了一個快速修復。

運行問題中發佈的重定位函數後，我運行了另一個解決問題的函數。新函數遍歷樹的所有級別並檢查節點是否靠得太近。如果是，則該算法找到最接近的共同祖先，並且增加其左側和右側兒童之間的距離。在此之後，節點之間不再有碰撞。

來源

2017-06-02 23:11:34 Daniel

如何動態地重新定位二叉樹節點

回答

相關問題