题目1090：路径打印。N叉树

从此醉

浏览: 1044806 次
性别:
来自: US

最近访客更多访客>>

billyhhzh

u012363178

devcang

宝帅啊啊啊

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

题目描述：

给你一串路径，譬如：
a\b\c
a\d\e
b\cst
d\
你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右缩一格，就像这样：
a
b
c
d
e
b
cst
d
同一级的需要按字母顺序排列，不能乱。

输入：

每个测试案例第一行为一个正整数n（n<=10）表示有n个路径，当n为0时，测试结束，接下来有n行，每行有一个字串表示一个路径，长度小于50。

输出：

输出目录结构，每一个测试样例的输出紧跟一个空行。

样例输入：

4
a\b\c
a\d\e
b\cst
d\
0

样例输出：

a
  b
    c
  d
    e
b
  cst
d

我在这里是是建了一个多叉树。兄弟节点之间是排序的。

自定义一个跟节点。每个节点都一个前缀(subString)，代表他们的路径，如果相同，则是同一个目录。

是用Java的TreeSet可以自动排序。

解释在代码注释里了。

网上也有用字典树的。还有一种简单的方法是a/b/c, 可以看成是文件 a，a/b，a/b/c 这样把所有的文件按照自定义规则排序，在输出就行了。

public class PathPrint_1090 {
	static int n;
	static Node root; //定义一个根节点
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextInt()) {
			n = scanner.nextInt();
			if(n == 0)
				break;
			String str;
			Node root = new Node();
			root.key = "";
			root.subString = "";
			root.children = new TreeSet<Node>();
			for (int i = 0; i < n; i++) {
				str = scanner.next();
				root.addChild(new Node(str.split("\\\\"), 0, root)); //将读入的一个字符串分割为一个字符数组，构造一个链表
			}
			root.print();
			System.out.println();
		}
	}
}

class Node implements Comparable<Node> {
	public String key; //需要输出的名称
	public String subString; //前缀，相同则为一个目录
	public TreeSet<Node> children; //子节点。个数不定
	public Node father; //父节点
	public int pre; //代表偏移量

	public int compareTo(Node o) { //定义比较函数。即比较前缀 a\b\ == a\b\, 是一个目录
		return this.subString.compareTo(o.subString);
	}
	public Node() {}
	//根据一个字符数组，构造一个节点串. 
	public Node(String str[], int index, Node f) {
		this.subString = "";
		if (index == str.length) //到了最后就直接返回
			return;
		for (int i = 1; i <= index; i++)
			this.subString += str[i] + '\\'; //获得前缀
		if (index == 0)
			this.subString = str[0];
		this.key = str[index];
		this.pre = f.pre + f.key.length() + 1; //偏移量等于父节点的偏移量 +　父节点长度
		this.father = f;
		if (index != str.length) {
			if (this.children == null)
				this.children = new TreeSet<Node>();
			children.add(new Node(str, index + 1, this));
		}
	}

	public void addChild(Node n) {  //添加一个孩子节点
		//由于孩子节点可能重复，重新合并
		if (children.contains(n)) {
			Node temp = null;
			for (Node temp2 : children) {
				if (temp2.compareTo(n) == 0)
					temp = temp2;
			}
			temp.addChild(n.children.first());
		} else {
			children.add(n);
		}
	}
	public void print() {
		if (this.key == null)
			return;
		if(this.key != ""){
			pre--; //由于第一个位置会多个空格
			while (pre-- > 0)
				System.out.print(" ");
			System.out.println(key);
		}
		if (this.children != null && children.size() > 0) {
			for (Node n : children)
				n.print();
		}
	}
}

分享到：