随机化文本文件以避免不平衡树

Question

当前，我有一个从文本文件中阅读的电影列表。这是一个示例：

Forrest Gump/1994/PG-13/142/8.8/Tom Hanks
Star Wars/1977/PG/121/8.7/Mark Hamill,Carrie Fisher,Harrison Ford
Jaws/1975/PG/124/8.1/

我被告知，在将文本添加到二进制搜索树中之前，我应该随机对文本进行随机，以免拥有不平衡的树，这就是我要完成的。我没有阅读文件的问题，我只需要帮助弄清楚如何随机化文本。我最初的想法是将其存储到和ArrayList中，然后随机填充它，但我无法完全想到实现。这是我从文本文件中阅读的地方：

try{
        Scanner read = new Scanner( new File("movies.txt") );
        do{
            ArrayList<String> actorList = new ArrayList<String>();
            String line = read.nextLine();
            String [] tokens = line.split("/");
            if ( tokens.length == 6 ){
                actorList.addAll( Arrays.asList( tokens[5].split(",") ) );
            }
            // BEFORE ADDING TO TREE I WANT TO RANDOMIZE HERE
            tree.add( new Movie(tokens[0], Integer.parseInt(tokens[1]), tokens[2], Integer.parseInt(tokens[3]), 
                    Double.parseDouble(tokens[4]), actorList ));
        }while( read.hasNext() );
        read.close();
    }catch( FileNotFoundException fnf ){
        System.out.println("File not found.");
    }

BST类：

public class BinarySearchTree {
/**
 * The head of the tree.
 */
private Node root;
/**
 * Constructor that declares the head of tree to null.
 */
public BinarySearchTree() {
    root = null;
}
/**
 * Returns null if head of tree is empty.
 * @return null if head of tree is empty.
 */
public boolean isEmpty(){
    return root == null;
}
/**
 * Adds a Movie to the tree.
 * @param w The Movie object to be added.
 */
public void add( Movie m ){
    root = add( m,root );
}
/**
 * Helper function for adding a Movie to the search tree.
 * @param w The Movie to be added.
 * @param tree The root of the binary search tree.
 * @return The tree with the added values.
 */
private Node add( Movie m, Node tree ){
    if( tree == null ){
        return new Node(m);
    }else{
        if ( m.compareTo( tree.getData() ) <= 0 ){
            tree.setLeft( add( m, tree.getLeft() ));
        }else{
            tree.setRight( add( m, tree.getRight() ));
        }
        return tree;
    }
}
/**
 * Searches the tree recursively for a Movie object.
 * @param w The Movie object to search for.
 * @return Null if the Movie does not exist or the searched Movie if found.
 */
public Node search( Movie m ){
    if ( root == null ){
        System.out.println("No items to search.");
        return null;
    }else{
        return search( m, root );
    }
}
/**
 * Helper function for searching the tree for a Movie object.
 * @param w The Movie object to search for.
 * @param n The root of the search tree.
 * @return The Movie object if the searched Movie exists in the tree.
 */
private Node search( Movie m, Node n ){
    if ( m.compareTo( n.getData() ) == 0 ){
        if( n.getLeft() != null ){
           Node node = search(m, n.getLeft());
           if( node != null ){
               return node;
           }
        }
        return n;
    }
    if ( m.compareTo( n.getData() ) < 0 ){
        if( n.getLeft() == null ){
            System.out.println("Item not found.");
            return null;
        }else{
            return search(m, n.getLeft());
        }
    }else{
        if ( n.getRight() == null ){
            System.out.println("Item not found.");
            return null;
        }else{
            return search(m, n.getRight());
        }
    }
}

通过评分搜索电影：

    System.out.println("Select a rating: ");
    System.out.println("1. G");
    System.out.println("2. PG");
    System.out.println("3. PG-13");
    System.out.println("4. R");
    switch ( checkForMenu(1,4) ){
    case 1: rating = "G";
            break;
    case 2: rating = "PG";
            break;
    case 3: rating = "PG-13";
            break;
    case 4: rating = "R";
            break;
    }
    Movie temp = new Movie( "Unknown", 0, rating, 0, 0.0, null );
    Node leftMost = tree.search(temp);
    if( leftMost != null ){
           while(leftMost != null && temp.compareTo( leftMost.getData() ) == 0){
                System.out.println(leftMost.getData());
                leftMost = leftMost.getRight();
           }
    }

Answer 1

要"随机化"您的List，使用Collections.shuffle()：

List<Movie> movies = new ArrayList<>();
do {    
    //...                         // populate `movies`
    movies.add(new Movie(....)); 
} while (read.hasNext());
Collections.shuffle(movies);      // shuffle
for (Movie m : movies) {          // populate the tree
   tree.add(m);
}

这不会使您的树完全平衡，但是至少除了在有序的初始数据集的情况下，树成为链接的列表外，至少会使您的树。

Answer 2

免责声明： op已要求搜索所有具有特定评分的电影，并且可能对他有所帮助。根据他的评论I would appreciate if you can look over that and my search in BST to see why I don't get the output of all the movies when I search by rating.

看来您的树正在使用电影的名称作为钥匙，并且您想基于评分搜索，您需要对完整的树进行研究。但这将击败我们使用BST获得的对数搜索能力的目的。完整的搜索可以像：

一样写

private Movie searchBasedOnRating(String rating, Node currentNode)
{  
    Node result = null
    if (currentNode == null)
        return null;
    Movie movie = (Movie) currentNode.getData();
    if (movie.getRating().equals(rating)) 
        return movie ;
    if (currentNode.getLeft() != null)
        result = searchBasedOnRating(rating,currentNode.getLeft());
    if (result == null)
        result = searchBasedOnRating(rating,currentNode.getRight());
    return result;
}

您可以根据要求对其进行修改，但它应该在高水平上为您提供一个想法。您需要从root节点开始搜索使用完整的树。