如何從常規樹中創建二叉搜索樹

正如標題所述。我正嘗試從我創建的一般樹創建一個二叉查找樹。我一般節點類的代碼是：如何從常規樹中創建二叉搜索樹

Node<E> parent; 
E data; 
ArrayList<Node<E>> children = new ArrayList<Node<E>>(); 

public Node(E data){ 
    this.data = data; 
} 

public ArrayList<Node<E>> getChildren(){ 
    return this.children; 
} 

public void addChild(Node child){ 
    int counter = 0; 
    for (int i = 0; i < children.size(); i++){ 
     if (child.toString().equals(children.get(i).toString())){ 
      System.out.println("already exists"); 
      counter++; 
     } 
    } 
    if (counter > 0){} 
    else{ 
     children.add(child); 
    } 

} 

public void removeChild(Node<E> child){ 
    children.remove(child); 
} 

public Node<E> getChild(Node<E> child){ 
    for (int i = 0; i < children.size(); i++){ 
     if (children.get(i) == child){ 
      return child; 
     } 
    } 
    return null; 
} 

public void setParent(Node parent){ 
    this.parent = parent; 
} 

public Node<E> getParent(){ 
    return this.parent; 
} 

public boolean isDirectory(Node node){ 
    if (data == node.data){ 
     return false; 
    } 
    return true; 
} 

public boolean hasChildren(){ 
    return getChildren() != null; 
} 

public E getData(){ 
    return this.data; 
} 

public String toString(){ 
    return data.toString(); 
} 
}//end class

而且我的樹類是滿的方法得滿滿的，所以要保存所有你們的眼睛疲勞，我的樹類由根，並且它設置構造根作爲樹的根。我知道要將一般樹轉換爲二叉搜索樹，我必須將我的一般樹根設置爲二叉搜索樹的根。我的問題是，我從哪裏去？我如何遍歷我的一般樹來將節點添加到二叉搜索樹？任何幫助，將不勝感激。

來源

2014-12-11 user3554599

只要讓每一個非二進制樹節點分割成二進制節點（每兩個連續排序的孩子可以用二進制節點孩子一個孩子被替換），直到它不能/不應該分（因爲它是一個二進制節點） - 每個定義都不需要對BST進行平衡，但是每個任務可能會應用其他限制。見http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree用於進行旋轉的各種方式如果樹需要在年底進行平衡。 – user2864740 2014-12-11 06:05:07

在二叉搜索樹，你需要的東西是存儲（例如：數據）和搜索鍵的基礎上樹順序。這裏你的鑰匙是什麼？ – 2014-12-11 07:11:36

一般的樹是不是二進制，因爲它可以有子節點的任意數，是不是搜索因爲它的節點並沒有任何特定的順序。因此，從一般樹構造二叉查找樹就像在二叉查找樹中插入一般樹的所有節點一樣。請注意，我不會稱這轉換它是更多構造二叉搜索樹從一般樹中的節點。

來源

2014-12-11 09:20:04

我將如何去把所有的節點插入到二叉樹中呢？ @Ivaylo Strandjev – user3554599 2014-12-11 16:16:39

如何從常規樹中創建二叉搜索樹

回答

相關問題