送分了，java字符串的树排序,解决思路

送分了，java字符串的树排序,急！！
本帖最后由 zhanglu201112 于 2013-05-19 11:09:11 编辑 排序前：
A
A,D
A,D,C
A,B
A,B,C
A,D,E
要求排序后的效果：
A
A,D
A,D,C
A,D,E
A,B
A,B,C
就相当于一棵树一样，最多有九层，A底下有A,D，A,D底下又有A，D,C.... 不可以打乱原来的顺序。上面例子中，A，D在前面，排序后的A，D也要在前面，不能是A,B在前面。 排序 字符串 树
[解决办法]
根据输入顺序建trie树，然后前序遍历输出
[解决办法]
亲你需要什么效果啊，描述清楚点，看看之前有又遇到过了没有
[解决办法]
楼主,你的输入是什么? 是一个集合,还是一棵树? 你的输出是什么? 是一个序列,还是一棵树?
[解决办法]
对于字符串数组中的两个元素 A[i] 和 A[j], 你如何定义它们的大小？从题意看，不是字典序。
[解决办法]
我明白了.楼主可以先建树,再先序遍历.
树是一树普通多叉树,每个结点可有值域、长子指针、兄弟指针三部分：
struct CNode
{
    char m_Value;  // 值
     char m_IsString;
     CNode * m_Son;  // 长子指针
     CNode * m_Bro;  // 兄弟指针
};

然后定义一个根
CNode Root;
它的各个初值为空
Root.m_Value=0;
Root.m_IsString=0;
Root.m_Son=NULL;
Root.m_Bro=NULL;

然后对于输入串组 char * s[] 执行：
   for (i=0;s[i]!=NULL;i++)  // 把所有串插入树中
   {
      Insert(&Root,s[i]);
   }

建树函数：
void Insert(CNode * pRoot,char *s)
{
    char c;
    int i;
    CNode * r;
    CNode * p;

    for (i=0;c=s[i];i++)
    {
       for (r=NULL,p=pRoot->m_Son;p!=NULL,r=p,p=p->m_Bro)
       if (p->m_Value==c) break;
       if (p==NULL)    // 没有找到

        {
           p=new CNode;
           p->m_Value=c;
           p->m_IsString=0;
           p->m_Son=NULL;
           p->m_Bro=NULL;
           if (r==NULL) pRoot->m_Son=p; // 没有哥哥，自己是父亲的长子
           else r->m_Bro=p;              // 有哥哥，自己是哥哥的弟弟
       }
       pRoot=p;
    }
    pRoot->m_IsString=1;              // 把“串”标志置 1
}

上面插入的过程，与原始串序一致。
楼主所谓的“排序”，就是对 Root 的先序遍历:
  char Buf[256];
  Travel(&Root,Buf,0);

函数 Travel 如下：
void Travel(CNode * p,char Buf[],int n)
{
    CNode * q;

    Buf[n]=p->m_Value;
    n++;
    if (p->m_IsStirng) 输出 Buf[1] 到 Buf[n], 它是一个串；
    for (q=p->m_Son;q!=NULL;q=q->m_Bro)
    {
      Travel(q,Buf,n);
    }
}



[解决办法]

/**
 * 
 * @author xiazdong
 *
 */
public class Tree{

class Node{
Node child[] = new Node[26];//存储指向下面26个节点的指针
int n ; //存储以此节点为根的子树下面有多少个字符串
boolean flag;//此节点是否为字符串
char ch;
String value;//存储该节点的字符串
public Node(){
flag = false;
n = 0;
value = "";
ch = '0';
}
}
Node root;
public Tree(){
root = new Node();//根节点在初始时就建好了
root.ch='r';
for(int i=0;i<26;i++)
root.child[i] = new Node();
}
/**
 * 插入word
 * O(n) n为word的长度
 * @param word
 */
public void insert(String word){
System.out.println("插入:"+word);
int n = word.length(); 
 
Node current;
if(n==0) return;
current = root;
for(int i=0;i<n;i++){
char c = word.charAt(i);
for(int j=0;j<current.child.length;j++){
if(current.child[j].ch!='0' && current.child[j].ch==c){
current = current.child[j];
break;
}
else if(current.child[j].ch=='0'){
current.child[j].ch = c;
current.child[j].value = current.value+c;
current = current.child[j];
if(current.child[0]==null){
for(int a=0;a<26;a++)
current.child[a] = new Node();
}
break;
}
}
}
current.n++;
}
/**
 * 对以node为根的子树进行字典排序
 * O(n) n为树的节点个数
 * @param node以此为根的子树
 */
public void preorder(Node node){
if (node==null 
[解决办法]
 node.ch=='0'){
return;
}
for(int i=0;i<26;i++){
if (node.child[i]!=null && node.child[i].ch!='0'){
System.out.println(node.child[i].value);
preorder(node.child[i]);
}
}
}
/**
 * 获得trie树中目前有多少个单词
 * O(1)
 * @return
 */
public int getSize(){
return root.n;
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert("A");
tree.insert("AD");
tree.insert("ADC");
tree.insert("AB");
tree.insert("ABC");
tree.insert("ADE");
tree.preorder(tree.root);
}
}