二叉搜索樹和中序遍歷

Question

我試圖快速實現Java中的二叉搜索樹。什麼是最好的類使用，有順序遍歷的方法？ （我聽說過TreeMap類，但它看起來像類不包含任何方法來按順序遍歷）。

Answer 1

使用LinkedHashMap的遍歷廣告訂單或TreeMap的比較順序 http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

Answer 2

我不認爲任何標準庫可用於這個穿越。檢查此鏈接的示例實現http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html

Answer 3

您可以隨時創建自己的類並使用該類實現算法。

public class Node { 
    Node leftChild; 
    Node rightChild; 
    int parent; 

    Node(int parent) { 
     this.parent = parent; 
    } 
} 

然後實現Binary Search Tree類。這個過程非常快，但它是給你一個想法。

public class BSTree { 
Node root; 

BSTree() { 
    root = null; 
} 

public void insert(Node node, int value) { 
    if (value >= node.parent) { 
     if (!(node.rightChild == null)) { 
      insert(node.rightChild, value); 
     } else { 
      node.rightChild = new Node(value); 
     } 
    } else if (value < node.parent) { 
     if (!(node.leftChild == null)) { 
      insert(node.leftChild, value); 
     } else { 
      node.leftChild = new Node(value); 
     } 
    } else { 
     root = new Node(value); 
    } 
} 


public boolean delete(Node node, int value) { 
    if (root == null) { 
     return false; 
    } else if (value > root.parent) { 
     return delete(root.rightChild, value); 
    } else if (value < root.parent) { 
     return delete(root.leftChild, value); 
    } else { 
     if (root.leftChild == null && root.rightChild == null) { 
      root = null; 
      return true; 
     } else if (root.leftChild == null && root.rightChild != null) { 
      root = root.rightChild; 
      return true; 
     } else if (root.leftChild != null && root.rightChild == null) { 
      root = root.leftChild; 
      return true; 
     } else { 
          Node minRight = minNode(root.rightChild); 
          root = minRight; 
          delete(minRight, minRight.parent); 
          return true; 
     } 
    } 
} 

public Node minNode(Node node) { 
    if (node.leftChild == null) { 
     return node; 
    } else { 
     return minNode(node.leftChild); 
    } 
} 
} 

Answer 4

TreeSet類可能是你想要什麼

class Node implements Comparable<Node>; // implements your Node class 
TreeSet<Node> set = new TreeSet<Node>(); 

// after adding a bunch of nodes into set 
Iterator<Node> it = set.iterator(); 
while(it.hasNext()){ 
    Node current = it.next(); 
    System.out.println(current); // operate on current node 
} 

Node first = set.first(); // smallest element in set 
Node second = set.ceiling(first); // the successor method