二叉树括号表示的反序列化 - JAVA

(1(2(4)())(3(6)()))可以表示一颗二叉树如下图：

将其反序列化，从硬盘读入导入内存。这样方便我们练习二叉树的各种算法。

这次算法本书对二叉树的递归性，栈的在括号匹配中的使用亦是非常好的练习案例

我记得上大学时，有老师演示过外国人写的叫ptree的小工具，可以从文件读二叉树的括号表达解析为二叉树内存结构（如本例实现），然后在屏幕输出字符画面的树。

好像是用管道给输入的， cat data.txt | ptree

我也找到过那个链接，但不能下载了。自己动手写一个吧。输出的程序我后面补上。

package lee.tree;  
  
import java.io.BufferedReader;  
import java.io.FileInputStream;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
import lee.tools.ArrayStack;  
import lee.tools.Stack;  
  
public class BiTree {  
    public int data;  
    public BiTree left;  
    public BiTree right;  
      
    public static BiTree initTree(String path) throws IOException{  
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));  
        String treeString = br.readLine();  
        char[] tChars = treeString.toCharArray();  
        System.out.println(tChars);  
        BiTree bt =  getTree(tChars, 0 , tChars.length-1 );  
        return bt;  
    }  
      
    static BiTree getTree(char[] tChars , int left , int right){  
        if(right-left<2){  
            return null;  
        }  
        else if(right-left==2){  
            BiTree root = new BiTree();  
            char[] dataChar =  new char[1];  
            dataChar[0] = tChars[left+1];  
            root.data = Integer.parseInt(new String(dataChar));  
            return root;  
        }  
        else{  
            BiTree root = new BiTree();  
            int l_left = left+2;  
            int l_right = parenthesesMatch(tChars,l_left);  
            int r_left = l_right+1;  
            int r_right = parenthesesMatch(tChars,r_left);  
            char[] dataChar =  new char[1];  
            dataChar[0] = tChars[left+1];  
            root.data = Integer.parseInt(new String(dataChar));  
            root.left = getTree(tChars, l_left , l_right);  
            root.right = getTree(tChars, r_left ,r_right );  
            return root;  
        }  
    }  
      
    public static int  parenthesesMatch(char[] str ,int i){  
        Stack stack = new ArrayStack();  
        stack.push(i);  
        i++;  
        while(!stack.isEmpty()){  
            if(str[i]=='('){  
                stack.push(i);  
            }  
            else if(str[i]==')'){  
                stack.pop();  
            }  
            i++;  
        }  
        return i-1;  
    }  
      
    static public void printTree(){  
          
    }  
}