数据结构与算法：手机上每个数字对应几个字母,给你一串数字,请你输出所有可能的字符串（树结构处理）

题目:手机上每个数字对应几个字母,给你一串数字,请你输出所有可能的字符串

 

 

 

 

package com.test;

import java.util.ArrayList;
import java.util.List;


/**
 * @author jsczxy2
 *
 */
public class TestTelNumber {
	
	public static void main(String[] args) {
		String str = "154767";
		Node node = new Node(' ');
		char cs[] = str.toCharArray();
		for(char c : cs){
			addNodes(node,c);
		}
		order(node);
		
	}
	
	public static void order(Node node){
		//如果有子节点继续遍历子节点
		if(node.hasChildren()){
			List<Node> children = node.getChildren();
			for(Node nd : children){
				order(nd);
			}
		}else{
			//如果没有子节点也就是一次数字的完成，直接打印出该子节点一直到根节点的路径
			StringBuffer sb = new StringBuffer();
			Node me = node;
			while(true){
				if(me.getParent()!=null){
					sb.append(String.valueOf(me.getC()).trim());
					me = me.getParent();
				}else{
					break;
				}
			}
			System.out.println(sb.reverse().toString());
		}
	}
	
	public static void addNodes(Node node,char c){
		//没有子节点直接赋予子节点
		if(!node.hasChildren()){
			node.setChildren(createNodes(String.valueOf(c),node));
		}else{
			//有子节点遍历子节点继续递归每个子节点
			List<Node> children = node.getChildren();
			for(Node nd : children){
				addNodes(nd,c);
			}
		}
	}
	
	//根据number创建子节点
	public static List<Node> createNodes(String number,Node parent){
		List<Node> list = new ArrayList<Node>();
		if("0".equals(number)){
			list.add(new Node(' ',parent));
		}else if("1".equals(number)){
			list.add(new Node(' ',parent));
		}else if("2".equals(number)){
			list.add(new Node('a',parent));
			list.add(new Node('b',parent));
			list.add(new Node('c',parent));
		}else if("3".equals(number)){
			list.add(new Node('d',parent));
			list.add(new Node('e',parent));
			list.add(new Node('f',parent));
		}else if("4".equals(number)){
			list.add(new Node('g',parent));
			list.add(new Node('h',parent));
			list.add(new Node('i',parent));
		}else if ("5".equals(number)){  
			list.add(new Node('j',parent));  
			list.add(new Node('k',parent));  
			list.add(new Node('l',parent));  
        } else if ("6".equals(number)){  
            list.add(new Node('m',parent));  
            list.add(new Node('n',parent));  
            list.add(new Node('o',parent));  
        } else if ("7".equals(number)){  
            list.add(new Node('p',parent));  
            list.add(new Node('q',parent));  
            list.add(new Node('r',parent));  
            list.add(new Node('s',parent));  
        } else if ("8".equals(number)){  
            list.add(new Node('t',parent));  
            list.add(new Node('u',parent));  
            list.add(new Node('v',parent));  
        } else if ("9".equals(number)){  
            list.add(new Node('w',parent));  
            list.add(new Node('x',parent));  
            list.add(new Node('y',parent));  
            list.add(new Node('z',parent));  
        } 
		return list;
	}
	
}

class Node{
	
	private char c;
	
	private List<Node> children = new ArrayList<Node>();
	
	private Node parent = null;
	
	public Node(char c) {
		this.c = c;
	}
	
	public Node(char c,Node parent) {
		this.c = c;
		this.parent = parent;
	}

	public char getC() {
		return c;
	}

	public void setC(char c) {
		this.c = c;
	}

	public List<Node> getChildren() {
		return children;
	}

	public void setChildren(List<Node> children) {
		this.children = children;
	}
	
	public Node getParent() {
		return parent;
	}

	public void setParent(Node parent) {
		this.parent = parent;
	}

	public boolean hasChildren(){
		return this.children.size()>0?true:false;
	}
}