通過BST搜索

我創建了一個BST，它將每個節點設置爲一個字符串值，我想知道是否有一種方法可以在樹中搜索，但一次只能搜索一個值。所以說節點中的字符串是「卡車」，有沒有辦法在樹中搜索並返回「t」？這是我的代碼具有興建樹：通過BST搜索

public class BinaryTree { 

public Node root; 
public BinaryTree tree; 
public static int pos; 
public static Node[] theArray; 

private static class Node { 
    Node left; 
    Node right; 
    String data; 

    Node(String s) { 
     left = null; 
     right = null; 
     data = s; 
    } 
} 

public BinaryTree plantTree(ArrayList<String> dict) { 

    tree = new BinaryTree(); 

    Collections.shuffle(dict); 

    for (String s : dict) { 
     s.toUpperCase(); 
     tree.add(s); 
    } 

    return tree; 

} 

/** 
* Creates an empty binary tree 
*/ 
public BinaryTree() { 
    root = null; 
} 

public void add(String data) { 
    root = add(root, data); 
} 

private Node add(Node node, String data) { 
    if (node == null) { 
     node = new Node(data); 
    } else { 
     if (data.compareTo(node.data) > 0) { 
      node.left = add(node.left, data); 
     } else { 
      node.right = add(node.right, data); 
     } 
    } 

    return (node); 
}

}

來源

2012-03-21 Ryan Sayles

你的問題不清楚 – Adrian 2012-03-21 20:37:55

也許我誤解了你的問題，但它聽起來像你想要的東西遍歷樹。我會使用訪問者模式。（這聽起來像是功課，所以爲什麼不使用標準模式:)）

public class Node<T>{ 
... 
    public void visitDepthFirst(Visitor<T> v){ 
     v.visit(this); 
     if (left != null){ 
      left.visitDepthFirst(v); 
     } 
     if (right != null){ 
      right.visitDepthFirst(v); 
     } 
    } 
} 

interface Visitor<T>{ 
    public void visit(T t); 
} 
... 
Node<String> root = ...; 
root.visitDepthFirst(new Visitor<String>(){ 
    public visit(String val){ 
     if ("truck".equals(val)){ 
      // do something 
     } 
    } 
});

我會讓你找出廣度搜索。此外，使用泛型的節點類將更加有用。而你的班級結構有點混亂。我建議你只使用節點AS樹本身。畢竟，樹中的每個節點都是樹本身。（閱讀有關複合模式）

來源

2012-03-21 21:16:05 JohnnyK

這樣看來，你試圖通過僅第一個字母，通過你的樹進行搜索。這隻要返回整個單詞就可以了。所以你仍然需要使用BST遍歷或搜索算法。

來源

2012-03-21 21:15:57 woolcock66

所以說，在一個節點的字符串是「卡車」有沒有辦法來搜索通過樹，並返回「T」？

真的，我不知道這個問題是關於什麼。
如果您有BST，那麼您可以使用二分搜索進行搜索。就是這樣。

如果找到該元素，則二分查找返回true。如果值不是樹的一部分，您可以實現自己的BST，不返回boolean，而是返回Char，如t中的問題，null。

來源

2012-03-22 16:51:01 Cratylus

通過BST搜索

回答

相關問題