Получение количества повторяющихся строк в двоичном дереве

Поэтому я должен прочитать файл и поместить его в двоичное дерево, что я уже сделал. Для второй части мне нужно пересечь дерево и вывести количество повторений каждой строки.

Читать в файле:

test sentence this is for binary trees this is a test sentence this this is 

Представление о том, как это должно выглядеть:

this = 4;
test = 2;
sentence = 2;
is = 3;

вот мой код:

// A binary tree node
class Node {

String data;
Node left, right;

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


import java.util.*;
import java.io.*;
class BinaryTree {

static Node root;
static int preIndex = 0;

//tree builder
Node buildTree(String strArr[], int inStrt, int inEnd) {

    if (inStrt > inEnd) {
        return null;
    }

    /* Pick current node from Preorder traversal using preIndex
     and increment preIndex */
    Node tNode = new Node(strArr[preIndex++]);

    /* If this node has no children then return */
    if (inStrt == inEnd) {
        return tNode;
    }

    /* Else find the index of this node in Inorder traversal */
    int inIndex = search(strArr, inStrt, inEnd, tNode.data);

    /* Using index in Inorder traversal, construct left and
     right subtress */
    tNode.left = buildTree(strArr, inStrt, inIndex - 1);
    tNode.right = buildTree(strArr, inIndex + 1, inEnd);

    return tNode;
}

int search(String[] strArr, int strt, int end, String value) {
    int i;
    for (i = strt; i <= end; i++) {
        if (strArr[i] == value) {
            return i;
        }

    }
    return i;
}

//print function
void printInorder(Node node) {
    if (node == null) {
        return;
    }

    /* first recur on left child */
    printInorder(node.left);

    /* then print the data of node */
    System.out.print(node.data + " ");

    /* now recur on right child */
    printInorder(node.right);
}

// driver program to test above functions
public static void main(String args[]) throws IOException{
    BinaryTree tree = new BinaryTree();
    Scanner inFile = new Scanner(new File("testSentence.txt"));
    int i = 0;
    String strArr[] = new String[15];

    while(inFile.hasNext()){
      strArr[i] = inFile.next();
      i++;
    }


    /* Testing ArrayList
     * for(int i = 0; i < strArr.size(); i++){
      System.out.println("Word " + i + " = " + strArr.get(i));

    }*/


    int len = strArr.length;
    Node mynode = tree.buildTree(strArr, 0, len - 1);

    // building the tree by printing inorder traversal
    System.out.println("Inorder traversal of constructed tree is : ");
    tree.printInorder(mynode);

}      
}

Выход:

Inorder traversal of constructed tree is : 
test sentence this is for binary trees this is a test sentence this this is 

1 ответ

  1. Вы можете иметь метод в BinaryTreeклассе, который принимает хэш-карту строки в целое число, которое отслеживает частоты слов.

    public void getStringFreq (Node node, Map<String, Integer> map)
    {
        if (node == null) {
           return;
        }
    
       /* left child */
       getStringFreq(node.left, map);
    
       /* get the data of node */
       String s = node.data;
    
       Integer i = map.get(s); // have we mapped it yet
    
       // not yet
       if (i == null)
          map.put(s, 1);
       // already mapped, increment freq
       else
          map.put(s, i + 1);
    
       /* right child */
       getStringFreq(node.right, map);
    }
    

    Вызовите его с:

    Map<String, Integer> map = new HashMap<String, Integer> ();
    tree.getStringFreq(mynode, map);
    System.out.println(map);
    

    Выход:

    {предложение=2, a=1, test=2, binary=1, this=4, for=1, is=3, trees=1}