如何在Java中將節點插入完整的二叉樹？

衆所周知，當插入一個完整的二叉樹時，我們必須從左到右填充所有葉子的所有子元素。我有以下方法將節點插入完整的二叉樹。如何在Java中將節點插入完整的二叉樹？

//fields 
private T item; 
private int size; 
private CBTree<T> left, right; 

//add method 
public void add(T item) 
{ 
    if(left == null) 
    { 
     left = new CBTree<T>(item); 
     size += left.size; 
    } 
    else if(right == null) 
    { 
     right = new CBTree<T>(item); 
     size += right.size; 
    } 
    else if(!((left.left != null) && (left.right != null)) && 
      ((right.left == null) || (right.right == null))) 
    { 
     left.add(item); 
    } 
    else 
    { 
     right.add(item); 
    } 
}

這個實現的問題是，在第11屆節點後，增加了12節點的8，而不是6，左側孩子，我明白，這是因爲發生在下面的行重新分配這棵樹的根成爲根的左邊孩子。

left.add(item);

所以它將根改爲2.有沒有辦法將根改回原來的值？我正在嘗試在不使用堆棧和隊列的情況下完成此操作。

來源

2017-04-07 Buttyfade

可能重複？ http://stackoverflow.com/questions/20890929/how-to-implement-a-complete-binary-tree-using-recursion-without-comparing-the-va –

@JimMischel我的問題不同於你鏈接的問題。他們的解決方案看起來與我的同一個地方失敗。此後，我已經想出了實施該方法的正確方法，這要感謝Dukeling。我將稍後發佈解決方案。 – Buttyfade

感謝Dukeling的回答，實現此方法的正確方法是從數學角度確定子樹是否已滿。這裏是代碼：

//fields 
private T item; 
private int size; 
private CBTree<T> left, right; 

//add method 
public void add(T item) 
{ 
    if(left == null) 
    { 
     left = new CBTree<T>(item); 
    } 
    else if(right == null) 
    { 
     right = new CBTree<T>(item); 
    } 
    else if(leftFull()) 
    { 
     right.add(item); 
    } 
    else 
    { 
     left.add(item); 
    } 
    size++; 
} 

//Checks if the left subtree is full 
public boolean leftFull() 
{ 
    int used, leafs = 1; 
    while(leafs <= size + 1) 
    { 
     leafs *= 2; 
    } 

    leafs /= 2; 
    used = (size + 1) % leafs; 
    if(used >= (leafs/2)) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
}

來源

2017-04-10 04:05:21 Buttyfade

僅僅檢查孩子的孩子以確定哪一邊要去哪裏是不夠的，因爲一旦樹達到高度4就不再工作，因爲根的孩子的孩子不會從這點向前，但我們仍然可以去左或右。

2的方法浮現在腦海中：

必須在每個節點的complete變量。

沒有孩子的節點已完成。

完成具有2個完全相同大小孩子的節點。

每當更新樹（插入或刪除）時，您也會爲每個受影響的節點更新此變量。
數學上根據大小確定子樹是否完整。

樹大小2^n - 1已完成（對於某些n）。

注意：如果我們不允許在不保留樹完整的情況下自由刪除元素，這將僅適用。

不管採用哪種方式，做一個插入的時候，我們去左（left.add(item)）如果這兩個條件都爲真：

左子樹是不完整的
左，右子樹大小相同（都是完整的，這意味着我們通過插入來增加高度）

我會將實施細節留給您。

注意：您還需要更新的大小做left.add(item);和right.add(item);時。你可能只需在add函數中添加一個size++，因爲我們添加了1個元素，所以無論大小如何，大小都增加1。

來源

2017-04-07 09:59:23 Dukeling

如何在Java中將節點插入完整的二叉樹？

回答

相關問題