一道关于树的面试题
??? 记得不久以前有道面试题，要求下面的数据结构
?
?
??? 里面每一项都是一个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());}}}}