一道关于树的面试题

??? 记得不久以前有道面试题，要求下面的数据结构

?
?
??? 里面每一项都是一个id和一个name，并且，要求能够通过name来返回id。

?

??? 我当时是用一个树结构来实现的，代码如下：

package cn.lettoo;import java.util.ArrayList;import java.util.List;public class TreeNode {    //父节点    private TreeNode parent = null;    private int id;    private String name;    // 子节点，一个节点可以有0至多个子节点    private List<TreeNode> children = new ArrayList<TreeNode>();    public int getId() {        return id;    }    public String getName() {        return name;    }    // 构造函数，通过传入的父结点来生成此父节点的子节点    public TreeNode(TreeNode parent, int id, String name) {        this.parent = parent;        this.id = id;        this.name = name;        if (parent != null) {            parent.children.add(this);        }    }    // 为当前节点加子节点    public TreeNode addChild(int id, String name) {        TreeNode child = new TreeNode(this, id, name);        return child;    }    // 通过name来查询树中是否有这样命名的节点，如果有，返回此节点。    public TreeNode hasChild(String name) {        if (name.equals(this.name)) {            return this;        }        // 这里使用递归的方法来遍历所有子节点，如果result有值，则跳出直接返回。        TreeNode result = null;        for (TreeNode child : this.children) {            result = child.hasChild(name);            if (result != null) {                break;            }        }        return result;    }    @Override    public String toString() {        StringBuffer sb = new StringBuffer();        sb.append(String.format("id=%d, ", this.id));        sb.append(String.format("Name=%s ", this.name));        if (!this.children.isEmpty()) {            sb.append(", children=[");            for (TreeNode child : this.children) {                sb.append(child.toString());            }            sb.append("]");        }        return sb.toString();    }}

?

??? 测试代码如下：

package cn.lettoo;import java.util.Scanner;/** * @author Jeffrey */public class TreeTest {    /**     * @param args     */    public static void main(String[] args) {        TreeNode tree = new TreeNode(null, 2, "sally");        // 2,sally -> 3,joe -> 5,mike -> 4,pat        TreeNode joe = tree.addChild(3, "joe");        TreeNode mike = joe.addChild(5, "mike");        TreeNode pat = mike.addChild(4, "pat");        // 3,joe -> 6,liz -> 18,alf -> 12,fred -> 15,con        TreeNode liz = joe.addChild(6, "liz");        TreeNode alf = liz.addChild(18, "alf");        TreeNode fred = alf.addChild(12, "fred");        TreeNode con = fred.addChild(15, "con");        // 18,alf -> 30,bob -> 20,tim -> 24,ned -> 22,kate        TreeNode bob = alf.addChild(30, "bob");        TreeNode tim = bob.addChild(20, "tim");        TreeNode ned = tim.addChild(24, "ned");        TreeNode kate = ned.addChild(22, "kate");        // 30,bob -> 36,sue        TreeNode sue = bob.addChild(36, "sue");        System.out.println(tree.toString());        System.out.println("Input \"exit\" to end.");        Scanner scanner = new Scanner(System.in);        do {            System.out.println("Please input a name.");            System.out.print(">>");            String name = scanner.next();            if (name.equalsIgnoreCase("exit")) {                break;            }            TreeNode result = tree.hasChild(name);            if (result == null) {                System.out                        .println(String                                .format("The tree node name \"%s\" do not in the tree. ",                                        name));            } else {                System.out.println(String.format(                        "The tree node name \"%s\" id is %d.", name,                        result.getId()));            }        } while (true);    }}

?

??? 当时这个实现应该是满足的要求，但不知道面试就没有了后话，我觉得可能我实现的方法有些笨拙。今天想起来，还是记录一下。以后有新的想法再更新之。

package cn.edu.hust.chart;import java.util.*;public class TestTreeMap {public static void main(String[] args) {// Creat a tree mapTreeMap tm = new TreeMap();// Put elements to the maptm.put(2, "sally");tm.put(3, "joe");tm.put(4, "pat");tm.put(6, "liz");tm.put(18, "alf");tm.put(12, "fred");tm.put(15, "con");tm.put(30,"bob");tm.put(20, "tim");tm.put(24, "ned");tm.put(22, "kate");tm.put(5, "mike");// Get a set of entriesSet set = tm.entrySet();// Get an iteratorIterator i = set.iterator();// Display elementswhile (i.hasNext()) {Map.Entry me = (Map.Entry) i.next();System.out.print(me.getKey() + ": ");System.out.println(me.getValue());}System.out.println("please input the name: ");Scanner sc = new Scanner(System.in);String name = sc.nextLine();Iterator iterator =set.iterator();while (iterator.hasNext()) {Map.Entry me = (Map.Entry) iterator.next();if (me.getValue().equals(name)) {System.out.println(name + " id: " + me.getKey());}}}}