一道关于树的面试题

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

 
 
    里面每一项都是一个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);
    }

}

 

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

评论

2 楼 lettoo 2011-10-17  

谢谢LS

1 楼 wywin100 2011-10-16  

我给的代码

package cn.edu.hust.chart;

import java.util.*;

public class TestTreeMap {
	public static void main(String[] args) {
		// Creat a tree map
		TreeMap tm = new TreeMap();
		// Put elements to the map
		tm.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 entries
		Set set = tm.entrySet();
		// Get an iterator
		Iterator i = set.iterator();
		// Display elements
		while (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());
			}
		}
	}
}