二叉搜索树解决硬木问题

一 原问题链接

Hardwood Species - POJ 2418 - Virtual Judgehttps://vjudge.net/problem/POJ-2418

二 输入和输出

1 输入

输入包括每棵树的物种清单，每行一棵树。物种名称不超过 30 个字符，不超过 10 000 种，不超过 1 000 000 棵树。

2 输出

按字母顺序输出植物种群中代表的每个物种的名称，然后是占所有种群的百分比，保留小数点后 4 位。

三 输入和输出样例

1 输入样例

Red Alder

Ash

Aspen

Basswood

Ash

Beech

Yellow Birch

Ash

Cherry

Cottonwood

Ash

Cypress

Red Elm

Gum

Hackberry

White Oak

Hickory

Pecan

Hard Maple

White Oak

Soft Maple

Red Oak

Red Oak

White Oak

Poplan

Sassafras

Sycamore

Black Walnut

Willow

2 输出样例

Ash 13.7931

Aspen 3.4483

Basswood 3.4483

Beech 3.4483

Black Walnut 3.4483

Cherry 3.4483

Cottonwood 3.4483

Cypress 3.4483

Gum 3.4483

Hackberry 3.4483

Hard Maple 3.4483

Hickory 3.4483

Pecan 3.4483

Poplan 3.4483

Red Alder 3.4483

Red Elm 3.4483

Red Oak 6.8966

Sassafras 3.4483

Soft Maple 3.4483

Sycamore 3.4483

White Oak 10.3448

Willow 3.4483

Yellow Birch 3.4483

四 算法设计

使用二叉搜索树，先将每个单词都存入二叉树中，每出现一次，就修改该单词所在节点 cnt，让它加1，最后通过中序遍历输出结果。

五 代码

package poj2418;

import java.util.Scanner;

public class Poj2418 {
    static int sum = 0;

    static node rt = new node();
    static String w;

    // 中序遍历
    static void midprint(node root) {//中序遍历
        if (root != null) {
            midprint(root.l);
            System.out.print(root.word);
            System.out.printf(" %.4f\n", ((double) root.cnt / (double) sum) * 100);
            midprint(root.r);
        }
    }

    // 二叉排序树的插入
    static public node insert(node root, String s) {
        if (root == null) {
            node p = new node(s, 1);
            p.l = null;
            p.r = null;
            root = p;
            return root;
        }
        // 一个临时节点指向根节点，用于返回值
        node tmp = root;
        node pre = root;

        while (root != null) {
            // 保存父节点
            pre = root;
            if (s.compareTo(root.word) > 0) {
                root = root.r;
            } else if ((s.compareTo(root.word) < 0)) {
                root = root.l;
            } else {
                root.cnt++;
                return tmp;
            }
        }
        // 通过父节点添加
        if (s.compareTo(pre.word) > 0) {
            pre.r = new node(s, 1);
        } else {
            pre.l = new node(s, 1);
        }
        return tmp;
    }

    public static void main(String[] args) {
        rt = null; // 一定要初始化
        Scanner scanner = new Scanner(System.in);
        while (true) {
            w = scanner.nextLine();
            if (w.equals("##")) {
                break;
            }
            rt = insert(rt, w);
            sum++;
        }
        midprint(rt);
    }
}

class node {
    String word;
    node l;
    node r;
    int cnt;

    public node() {
    }

    public node(String word, int cnt) {
        this.word = word;
        this.cnt = cnt;
    }
}

六 测试

1 输入

2 输出