关于二叉树问题

Question

对于字符串：(e((d,f)(c(b,a))))
生成的二叉树为：其中节点1-5是要补足的，值为1，叶子节点值为0。
请问如何生成这样的二叉树？

Answer 1

图片地址：
http://photo.sina.com.cn/photo/4fd35e6045ca947cf7369不知道怎么显示不出来。

Answer 2

有一点不太明白
(d,f)，d是左节点，f是右节点
(b,a)，b怎么是右节点，a怎么是左节点？？？？？
没规律啊，怎么用程序生成

Answer 3

我自己的思路是对于字符串：(e((d,f)(c(b,a)))) 带有“,”不太好处理，把“,”去掉，变为：(e((df)(c(ba))))。 然后因为括号的数目和要补足的节点数正好相等，用栈的方法，每次遇到“（”进行push，将“（”所在的位置压入栈中，然后遇到“）”进行POP,把与其对应的“）”的位置pop出来，然后第一组pop出(ba)中左括号位置，将(ba)换成节点g，g的左右子节点分为为a和b,然后变为：(e((df)(cg))) ，递归处理，即可。但是这样的问题是可以设置每个节点的左右子节点，但是最后因为补足的节点的不确定性和具体的一些问题，生成不了一棵二叉树。如果不明白的话按我的思路试一下，看看能不能解决这个问题。我都试了半个月了，还没解决，郁闷！
谢谢各位了！
希望各位多帮忙！
因为我也是刚刚学java半年时间，不太熟悉！

Answer 4

答：这个简单的问题，兄弟要用半个月？有点儿夸张啊。一会儿就行了。参考代码如下：class BTNode
{//二叉树结点
int data;//结点本身的数据
BTNode left,right;//左右儿子
public BTNode(){this(0);}
public BTNode(int data){this(data,null,null);}
public BTNode(int data,BTNode left,BTNode right)
{
 this.data=data;
 this.left=left;
 this.right=right;
 }
}
public class BTree {
    private String ds=null;//数据串。如：(e((d,f)(c(b,a))))# 注意：必须以#结束。表示没有数据了。
    private char ch;//当前要处理的字符
    private int pos=-1;//当前字符的位置。用于准确定位错误的位置
    private int no=0;//树中内部结点的编号。
    public BTree(String s){ds=s;}//构造器

    void nextChar()
    {//要处理的下一个字符
     ch=ds.charAt(++pos);
    }
    void p(String c)
    {//错误准确定位，且指出需要什么字符。
     System.out.println("在当前 "+pos+" 位置上期望需要字符："+c);
     System.exit(-1);
    }
    
    
    //能处理任意括号嵌套的指定形式的表达式。如：(e((d,f)(c(b,a))))# 注意：必须以#结束。表示没有数据了。
    BTNode  T()
    { char c1,c2;
     if(ch!='(') {p("(");}//若不是以(开始，准确报错。
     nextChar();
     if('a'<=ch && ch <='z' ){//若是字母
     c1=ch;//这是右子树的字母
     nextChar();
     if(ch==','){//若是,字符
     nextChar();
     if('a'<=ch && ch<='z'){//若是字母
     c2=ch;//这是左子树的字母
     nextChar();
     if(ch!=')'){p(")");}//若此时不是)结束，准确报错
     nextChar();
     BTNode l=new BTNode(c2);//构造左子树结点
     BTNode r=new BTNode(c1);//构造右子树结点
     return new BTNode(++no,l,r);//构造子树根结点，赋给编号。
    
     }//(F,F)形式处理完成
     else
     {p("字母");}//准确报错:需要量字母
     }else
     {//(F T)形式处理
       BTNode l=T();
       BTNode r=new BTNode(c1);
       return new BTNode(++no,l,r);
     }    
     }else
     {//(T T)形式处理
     BTNode r=T();
     BTNode l=T();
     return new BTNode(++no,l,r);
     }
       return null;
    }
    
    //这是一个中序遍历，用于测试构造的树是否正确。
    private void LDR(BTNode r )
    {
     if(r!=null)
     {
     LDR(r.left);
     if(r.left==null && r.right==null)
       System.out.print(" "+(char)r.data);
     else
       System.out.print(" "+r.data);
     LDR(r.right);
     }
    }
    
public static void main(String[] args) {
BTree tree=new BTree("(e((d,f)(c(b,a))))#");
tree.nextChar();
tree.LDR(tree.T());
}}
运行结果： a 2 b 3 c 4 f 1 d 5 e