关于二叉树问题2

Question

原帖见：
http://topic.csdn.net/u/20081127/18/6a28657b-22ed-4b57-b55a-c748c3d16937.html现在遇到新的问题，就是对于复杂表达式如((((e,f)n)o)(((a,b)g)((((j,k)(c,d))(h,i))l)))，用jiangnaisong兄弟的代码会报错，我个人解决不了，所以希望jiangnaisong见到帖子能帮忙解决。其他高手也欢迎参与哈！我自己对数据结构不太熟悉，所以自己无能为力。

Answer 1

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

Answer 2

2楼的代码就是jiangnaisong的代码吧？好像没有修改？这段代码处理简单的表达式如(e((d,f)(c(b,a))))没有问题，但是处理((((e,f)n)o)(((a,b)g)((((j,k)(c,d))(h,i))l)))的时候会报错。

Answer 3

答:很简单啊.我把代码简单改一下就行了.修改后的代码如下: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(); 
              if(ch!=')'){p(")");}//若此时不是)结束，准确报错 
              nextChar();
              BTNode r=new BTNode(c1); 
              return new BTNode(++no,l,r); 
            }                
            }else 
            {//(T F)或(T T)形式处理 
                BTNode r=T(); 
                if('a' <=ch && ch <='z'){//若是字母则是(T F)形式
                  c2=ch;//这是左子树的字母 
                     nextChar(); 
                     if(ch!=')'){p(")");}//若此时不是)结束，准确报错 
                     nextChar(); 
                     BTNode l=new BTNode(c2);//构造左子树结点 
                     return new BTNode(++no,l,r);//构造子树根结点，赋给编号。                
                }
                //此时必定是(T T)形式
                BTNode l=T(); 
                if(ch!=')'){p(")");}//若此时不是)结束，准确报错 
                nextChar();
                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()); 
        System.out.println();
        BTree tree1=new BTree("((((e,f)n)o)(((a,b)g)((((j,k)(c,d))(h,i))l)))#"); 
        tree1.nextChar(); 
        tree1.LDR(tree1.T()); 
       
    } } 程序运行结果:
a 2 b 3 c 4 f 1 d 5 e
l 11 i 9 h 10 d 7 c 8 k 6 j 12 g 5 b 4 a 13 o 3 n 2 f 1 e