java树的概念（二叉树）

     在最近的学习中，我接触到了树的概念并且学习了二叉树，了解了以下概念：
   1、树的结构(树是一种层次结构)：1)根节点 root  2)边（树枝） 3)叶子节点
      树的深度：根节点为1（3）
      树的阶：根为0（2）
      A、B、C均为根节点，A为BC的根节点，B为DE的根节点，C为FG的根节点
      单向链表也叫做退化树
   2、树的分类：
      1）分支划分：
         二叉树：完全二叉树，满二叉树，红黑树……
         非二叉树：B+树，B-树
   3、构建搜索二叉树的过程
      1）node:lChild,rChild,obj(数据)
      2）从根节点开始判断：A放为根节点，再加入B，进行比较，如果A小于B，则B成为A的根节点，A         为B的左子树，再加入C判断………
         注意：前提要定义好，如实现的权值（ASCII），是否趋向于构建一棵平衡的二叉树等

      通过学习，我实现了构建一棵表达式树，叶子节点全部为操作数据，而父节点均为操作符，并且   可以用中序遍历将其输出（目前求值输出的结果仅适用于此模式的表达式），同时，将这一表达式树打印在JFrame上面，代码如下：      public class ExpressionTree {
private String[] array = new String[100];//存放已经取出的内容
private int i=0;//用于标记array的位置
public static Node root;
private int[] arrayint = new int[array.length];
private char[] arraychar = new char[array.length];

/**
* 构建一棵表达式树
* 2+10*5-20/2
*/
public void buildTree(){
Node node = new Node("2");
Node node1 = new Node("10");
Node node2 = new Node("5");
Node node3 = new Node("20");
Node node4 = new Node("2");
//Node node5 = new Node()
//构建方式
Node node5 = new Node("+");
Node node6 = new Node("*");
Node node7 = new Node("-");
root = node7;
Node node8 = new Node("/");
//构建树
node7.setLchild(node5);
node7.setRchild(node8);
node5.setLchild(node);
node5.setRchild(node6);
node6.setLchild(node1);
node6.setRchild(node2);
node8.setLchild(node3);
node8.setRchild(node4);

node.setLchild(null);

System.out.println(root.getString());
System.out.println(root.getlChild().getString());
System.out.println(root.getrChild().getString());
System.out.println(root.getlChild().getlChild().getString());
System.out.println(root.getlChild().getrChild().getString());
System.out.println(root.getlChild().getrChild().getlChild().getString());
System.out.println(root.getlChild().getrChild().getrChild().getString());
System.out.println(root.getrChild().getlChild().getString());
System.out.println(root.getrChild().getrChild().getString());

}

/**
* 中序读出树中的节点
*/
public void readTree(Node node){
if(node.getString()!=" "){
if(node.getlChild()!=null && node.getrChild()!=null){
readTree(node.getlChild());
System.out.println(node.getString());
array[i] = node.getString();
i++;
readTree(node.getrChild());
}else{
System.out.println(node.getString());
array[i] = node.getString();
i++;
}
}
}

/**
* 求得所得到的表达式的值
* @return
*/
    public void getValue(){
    for(int m=0;m<array.length;m=m+2){
    if(array[m]!=null){
    arrayint[m] = Integer.parseInt(array[m]);
    System.out.println("I am arrayint[m]:"+arrayint[m]);
    }
    }
    for(int n=1;n<array.length;n=n+2){
    if(array[n]!=null){
    arraychar[n] = array[n].charAt(0);
    System.out.println("I am arraychar[n]:"+arraychar[n]);
    }
    }
    }
   
    /**
     * 计算方法
     */
    public void operate(){
    int j=0;
    char c = ' ';//取左边的运算符
    //char c1 = ' ';//取右边的运算符
    //取出存储的字符进行运算
    for(int m=0;m<array.length;m++){
    if(array[m]!=null){
    if(m%2==0){
        if(c==' '){
        j = arrayint[m];
        if(operate==0)
        arrayresult[d] = j;
        System.out.println("I am arrayresult[" +d+"]:"+j);
        d++;
        }else{
        //进行判断，看数字的两边是否有操作符
        if(m>=1){//即左右两边都有了操作符
        char cl = arraychar[m-1];
        char cr = arraychar[m+1];
        System.out.println("I am cl:"+cl);
        System.out.println("I am cr:"+cr);
        if(cl =='+' || cl=='-')
        l = 1;
        if(cr=='+' || cr=='-')
        r = 1;
        if(cl =='*' || cl=='/')
        l = 3;
        if(cr =='*' || cr=='/')
        r = 3;
        if(l>r){
        operate = l;
        //System.out.println("I am operate:"+operate);
        }else{
        operate = r;
        //System.out.println("I am operate:"+operate);
        }
        }
        System.out.println("I am m:"+m+"  oprater is:"+operate);
        if(c=='*' && operate==3){
        j = arrayint[m-2]*arrayint[m];
        arrayresult[d] = j;
        arrayint[m] = j;
        //System.out.println("I m *j:"+j);
        System.out.println("I am arrayresult[" +(d)+"]:"+j);
        d++;
        }else if(c=='/' && operate==3){
        j = arrayint[m-2]/arrayint[m];
        arrayresult[d] = j;
        arrayint[m] = j;
        System.out.println("I am arrayresult[" +(d)+"]:"+j);
        //System.out.println("I m /j:"+j);
        d++;
        }
        }
        }else{
        c = arraychar[m];
        }
    }
    }
    d = 0;//为了下面的计算，d变为0
    c = ' ';
    //先取出乘除法的值，再取出加减法的值
    for(int m=0;m<arrayresult.length;m++){
    if(arrayresult[d]!=0){
    if(m%2==0){
    j = arrayresult[d];//j=2
    if(c==' ' || c=='+' || c=='-'){
            d++;
            System.out.println("I am j:"+j);
    }
        if(m==0){
        k = j;//k=2,存放已计算的元素
        }
        if(c=='+'){
        j = k+j;
        k = j;
        System.out.println("I am +j:"+j);
        }
        if(c=='-'){
        j = k-j;
        k = j;
        System.out.println("I am -j:"+j);
        }
        System.out.println("I am k:"+k);
        }else{
        c = arraychar[m];//c='+'
        }
        System.out.println("I am value:"+k);
    }
   
        }
    }
   
   
    /**
     * 打印得到的数组
     */
    public void printArray(){
    for(int m=0;m<array.length;m++){
    if(array[m]!=null){
    System.out.println("I am:"+array[m]);
    }
    }
    }


   实现打印二叉树的代码如下：   import java.awt.Color;
   import java.awt.Font;
   import java.awt.FontMetrics;
   import java.awt.Graphics;
   import java.util.List;

   import javax.swing.JPanel;

   /**
    * TODO 同一层结点过多有BUG，应该对每一层的所有结点都进行个数统计，之后才绘制。
    *
    */
   public class TreePanel extends JPanel {

private Node tree; //保存整棵树
private int gridWidth = 80; //每个结点的宽度
private int gridHeight = 20; //每个结点的高度
private int vGap = 50; //每2个结点的垂直距离
private int hGap = 30; //每2个结点的水平距离

private int startY = 10; //根结点的Y，默认距离顶部10像素
private int startX = 0; //根结点的X，默认水平居中对齐

private int childAlign; //孩子对齐方式
public static int CHILD_ALIGN_ABSOLUTE = 0; //相对Panel居中
public static int CHILD_ALIGN_RELATIVE = 1; //相对父结点居中

private Font font = new Font("微软雅黑",Font.BOLD,14); //描述结点的字体

private Color gridColor = Color.BLACK; //结点背景颜色
private Color linkLineColor = Color.BLACK; //结点连线颜色
private Color stringColor = Color.WHITE; //结点描述文字的颜色
private int m=0;//统计某一层的节点数

/**
* 默认构造
*/
public TreePanel(){
this(null,CHILD_ALIGN_ABSOLUTE);
}

/**
* 根据传入的Node绘制树，以绝对居中的方式绘制
* @param n 要绘制的树
*/
public TreePanel(Node n){
this(n,CHILD_ALIGN_ABSOLUTE);
}

/**
* 设置要绘制时候的对齐策略
* @param childAlign 对齐策略
* @see tree.TreePanel#CHILD_ALIGN_RELATIVE
* @see tree.TreePanel#CHILD_ALIGN_ABSOLUTE
*/
public TreePanel(int childAlign){
this(null,childAlign);
}

/**
* 根据孩子对齐策略childAlign绘制的树的根结点n
* @param n 要绘制的树的根结点
* @param childAlign 对齐策略
*/
public TreePanel(Node n, int childAlign){
super();
setTree(n);
this.childAlign = childAlign;
}

/**
* 设置用于绘制的树
* @param n 用于绘制的树的
*/
public void setTree(Node n) {
tree = n;
}

//重写而已，调用自己的绘制方法
public void paintComponent(Graphics g){
startX = (getWidth()-gridWidth)/2;
System.out.println("I am m:"+m);
super.paintComponent(g);
g.setFont(font);
drawAllNode(tree, startX, g);
}

/**
* 递归绘制整棵树
* @param n 被绘制的Node
* @param xPos 根节点的绘制X位置
* @param g 绘图上下文环境
*/
public void drawAllNode(Node n, int x, Graphics g){
int y = n.getLayer()*(vGap+gridHeight)+startY;
int fontY = y + gridHeight - 5; //5为测试得出的值，你可以通过FM计算更精确的，但会影响速度

g.setColor(gridColor);
g.fillRect(x, y, gridWidth, gridHeight); //画结点的格子

g.setColor(stringColor);
g.drawString(n.toString(), x, fontY); //画结点的名字

if(n.hasChild()){
//要先得到这一层总共的节点数
List<Node> c = n.getChilds();
int size = n.getChilds().size();
int tempPosx = childAlign == CHILD_ALIGN_RELATIVE
? x+gridWidth/2 - (m*(gridWidth+hGap)-hGap)/2
: (getWidth() - m*(gridWidth+hGap)+hGap)/2;

int i = 0;
for(Node node : c){
m = m+size;
int newX = tempPosx+(gridWidth+4*hGap)*i+50; //孩子结点起始X
g.setColor(linkLineColor);
g.drawLine(x+gridWidth/2, y+gridHeight, newX+gridWidth/2, y+gridHeight+vGap); //画连接结点的线
drawAllNode(node, newX, g);
i++;
}
}
}

public Color getGridColor() {
return gridColor;
}

/**
* 设置结点背景颜色
* @param gridColor 结点背景颜色
*/
public void setGridColor(Color gridColor) {
this.gridColor = gridColor;
}

public Color getLinkLineColor() {
return linkLineColor;
}

/**
* 设置结点连接线的颜色
* @param gridLinkLine 结点连接线的颜色
*/
public void setLinkLineColor(Color gridLinkLine) {
this.linkLineColor = gridLinkLine;
}

public Color getStringColor() {
return stringColor;
}

/**
* 设置结点描述的颜色
* @param stringColor 结点描述的颜色
*/
public void setStringColor(Color stringColor) {
this.stringColor = stringColor;
}

public int getStartY() {
return startY;
}

/**
* 设置根结点的Y位置
* @param startY 根结点的Y位置
*/
public void setStartY(int startY) {
this.startY = startY;
}

public int getStartX() {
return startX;
}

/**
* 设置根结点的X位置
* @param startX 根结点的X位置
*/
public void setStartX(int startX) {
this.startX = startX;
}


      }
    （打印的输出效果如附件图）