table.java~12~

源程序（包括最初的版本

package treeandbtreedemo;

/**
 * <p>Title: 表</p>
 * <p>Description: 为了以后的树的作图，故需要计算各个节点的x和y的坐标值。由此设计了表数组</p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author liuli
 * @version 1.2(2005.6.30)计算x,y的值
 * @version 2.0(2005.7.5)加入图形界面
 * @version 2.1(2005.7.5)初步加入动画和线程,产生节点的遍历动画效果
 * @version 2.2(2005.7.6)在基础架构中添加了二叉树类，把树和二叉树两种结构分开来做了
 * @version 3.0 图形
 * @version 4.0(2005.7.11)  adjust,do the new x,y.
 */

import queue.*;
public class Table {
  protected TableNode tables[];
  protected int number;//节点个数
  protected int treeCeng; //树的高度
  protected WideHigh wh[];
  protected int path[];
  //protected int w0,h0;//第一层的w,h
  protected int paintTableWidth,paintTableHeight;
  protected int radius;

  //构造方法，固定的数组空间，后续最好加入空间的扩展方法
  public Table() {
    this(100);
  }

  public Table(int number) {
    tables = new TableNode[number];
    path=new int [number];
    //w0=120;h0=50;
    radius=10;
  }



  /**查找某个元素,找到，返回数组序号，否则返回-1*/
  int search(Object name) {
    int i;
    for (i = 0; tables[i].name != null && !tables[i].name.equals(name); i++) {
      ;
    }
    if (tables[i].name != null) {
      return i;
    }
    else {
      return -1;
    }
  }

  /**根据字符串构造二叉树表，记录各个节点的信息*/
  void creatBinaryTreeTable(String s){
    String fa, ch, flag; //双亲，孩子，左右小孩标识
    int i = 0;
    int j;
    int n = 0; //控制数组
    fa = s.substring(i, i + 1);
    ch = s.substring(i + 1, i + 2);
    flag = s.substring(i + 2, i + 3);
    for (; ch.compareTo("#") != 0; i += 3, fa = s.substring(i, i + 1),
         ch = s.substring(i + 1, i + 2), flag = s.substring(i + 2, i + 3)) { //当孩子为"#"时结束,每次循环读取一新三元组、
      if (fa.compareTo("#") == 0) {//头节点
        tables[0] = new TableNode(ch, -1, 1, 1, 1);
      }
      else {
        if (flag.compareTo("L") == 0||flag.compareTo("l") == 0 ) {//左小孩
          if ( (j = search(fa)) != -1) { //找出f双亲所在的序号
            tables[n] = new TableNode(ch, j, tables[j].ceng + 1, 2, 1);
          }
        }

       if (flag.compareTo("R") == 0||flag.compareTo("r") == 0 ){//右小孩
         if ( (j = search(fa)) != -1) { //找出f双亲所在的序号
            tables[n] = new TableNode(ch, j, tables[j].ceng + 1, 2, 2);
          }

       }
      }
      n++;//数组序号加1
    }
    this.number = n;
    this.treeCeng = tables[number - 1].ceng;
    adjustWH();////输入x,y的值
  }

  /**根据字符串构造树表，记录各个节点的信息*/
  void creatTreeTable(String s) {
    String fa, ch; //双亲和孩子所表示的字符串
    int i = 0; //控制循环语句
    //记录节点名字，双亲位置，所在层数
    int j;
    int n = 0; //控制数组
    fa = s.substring(i, i + 1);
    ch = s.substring(i + 1, i + 2);
    for (; ch.compareTo("#") != 0; i += 2, fa = s.substring(i, i + 1),
         ch = s.substring(i + 1, i + 2)) { //每两个取为一组
      if (fa.compareTo("#") == 0) {
        tables[0] = new TableNode(ch, -1, 1);
      }
      else {
        if ( (j = search(fa)) != -1) { //找出f双亲所在的序号
          tables[n] = new TableNode(ch, j, tables[j].ceng + 1);
        }
      }
      n++;
    }
    this.number = n;
    this.treeCeng = tables[number - 1].ceng;
    //记录在兄弟间的排行
    i = 0;
    while (tables[i] != null) {
      if (i == 0) {
        tables[i].SiblingNumbers = 1;
        tables[i].locate = 1;
      }
      else if (tables[i].parents != tables[i - 1].parents) {
        tables[i].locate = 1;
      }
      else {
        tables[i].locate = tables[i - 1].locate + 1;
      }
      i++;
    }
    //记录含有的兄弟个数
    tables[number - 1].SiblingNumbers = tables[number - 1].locate;
    for (i = number - 2; i > 0; i--) {
      if (tables[i].parents != tables[i + 1].parents) {
        tables[i].SiblingNumbers = tables[i].locate;
      }
      else {
        tables[i].SiblingNumbers = tables[i + 1].SiblingNumbers;
      }
    }
    //输入x,y的值
    adjustWH();
  }

  /**计算并调整宽度和高度(w,h)的值
   * 用了辅助类WH,记录静态的宽度和高度
   * 该方法计算每个节点的坐标,然后进行调整
   * 每个节点的度数<=5
   *
   * 2005.7.5
   * 经用图形测试，发现节点的坐标的算法还是不太合理！！
   * 决定换一种思路
   * 前面一样的做法，当重叠或交叉时，改变他们父亲所在层的w,的值。
   * ！！！但是当2w放不下那么多的节点时，就把第一层的w放大，从新进行一边各个节点的x,y调整
   * 然后用图形学的缩放原理缩小在画布之内
   *
   *
   * */
  void adjustWH() {
    wh = new WideHigh[treeCeng + 1]; //宽和高的数组
    int r=radius; //节点的半径
    int  x0 = 0, y0 = 0; //根节点的坐标,设为原点
    //int w = 150, h = 70; //根节点的宽和高,可调
    int dw=20,dh=5;//当发生交叉重叠时每次的三角形w,h的变化
    int newX = 0, newY = 0;//计算所得的节点坐标
    int pa;//节点的双亲位置
    int i;
    //
    setWH(120);//设置第一层的w
    /*int wi=w0,hi=this.paintTableHeight/(treeCeng+1);//设定的w,h 的值
    //构造WH表
    for (i = 1; i <= treeCeng; i++) {//第一层开始
      wh[i] = new WideHigh(wi,hi);
      //wh[i].setWH(w, h);
      wi = wi /2;
      hi = hi ;
    }*/
    //计算newX,newY
    tables[0].setXY(x0, y0);
    i = 1;
    while (tables[i]!= null) { //从第二个节点开始
      //初步设定默认的x,y的坐标值
      pa = tables[i].parents; //双亲的序号
      newX = getx(i);
      newY = tables[pa].y + wh[tables[pa].ceng].h; //father.x+father.h；
      tables[i].setXY(newX, newY);
      //检验是否会相交
      if (tables[i].ceng == tables[i - 1].ceng &&
          (tables[i].x - r < tables[i - 1].x + r)) {
        //如果层次相同且[i].x-r<[i-1].x+r的. 即重叠了
        while (tables[i].ceng == tables[i - 1].ceng &&
               (tables[i].x - r < tables[i - 1].x + r) &&
               wh[tables[pa].ceng].w >= 2 * r) {
          if (wh[tables[pa].ceng].w <= 2 * r) {
            break; //这里以后要修改！放大第一层的w,若超界，则进行图形的缩小
          }
          else {
            //调整parant.(w,h)
            //if( wh[tables[pa].ceng].w -dw>=4r)
            wh[tables[pa].ceng].w = wh[tables[pa].ceng].w - dw;
            wh[tables[pa].ceng].h = wh[tables[pa].ceng].h + dh;

            //调整[i].(x,y)
            newX = getx(i);
            newY = tables[pa].y + wh[tables[pa].ceng].h; //father.x+father.h；
            tables[i].setXY(newX, newY);

            //调整[i-1].(x,y)
            newX = getx(i - 1);
            newY = tables[pa].y + wh[tables[pa].ceng].h; //father.x+father.h；
            tables[i - 1].setXY(newX, newY);

            //继续回循环比较
          }
        }

          //调整parent.(w,h) 结束后，把[i]所在那层的前面的那些节点的坐标值按新的w,h再计算一次
          for (int j = i; tables[j].ceng == tables[i].ceng; j--) {
            pa = tables[j].parents; //双亲的序号
            newX = getx(j);
            newY = tables[pa].y + wh[tables[pa].ceng].h; //father.x+father.h；
            tables[j].setXY(newX, newY);
          }

        }
        i++;

    }


  }

  /**计算根节点之外的各节点的x值*/
  int getx(int i) {
    int newX = 0;
    int  pa;
    pa = tables[i].parents; //双亲的序号
    switch (tables[i].SiblingNumbers) {
      case 1: //兄弟个数为1
        if (tables[i].locate == 1) { //节点序号为1
          newX = tables[pa].x; //双亲的x 表示为fa.x
        }
        break;

      case 2: //兄弟个数为2
        if (tables[i].locate == 1) { //节点序号为1
          newX = tables[pa].x - wh[tables[pa].ceng].w; //father.x=father.w
        }
        if (tables[i].locate == 2) { //节点序号为2
          newX = tables[pa].x + wh[tables[pa].ceng].w; //father.x+father.w
        }
        break;

      case 3: //兄弟个数为3
        if (tables[i].locate == 1) { //节点序号为1
          newX = tables[pa].x - wh[tables[pa].ceng].w; //father.x-father.w
        }
        if (tables[i].locate == 2) { //节点序号为2
          newX = tables[pa].x; ; //father.x
        }
        if (tables[i].locate == 3) { //节点序号为3
          newX = tables[pa].x + wh[tables[pa].ceng].w; //father.x+father.w
        }
        break;

      case 4: //兄弟个数为4
        if (tables[i].locate == 1) { //节点序号为1
          newX = tables[pa].x - wh[tables[pa].ceng].w; //father.x-father.w
        }
        if (tables[i].locate == 2) { //节点序号为2
          newX = tables[pa].x - wh[tables[pa].ceng].w / 2; //father.x-father.w/2
        }
        if (tables[i].locate == 3) { //节点序号为3
          newX = tables[pa].x + wh[tables[pa].ceng].w / 2; //father.x+father.w/2
        }
        if (tables[i].locate == 4) { //节点序号为4
          newX = tables[pa].x + wh[tables[pa].ceng].w; //father.x+father.w
        }
        break;

      case 5: //兄弟个数为5
        if (tables[i].locate == 1) { //节点序号为1
          newX = tables[pa].x - wh[tables[pa].ceng].w; //father.x-father.w
        }
        if (tables[i].locate == 2) { //节点序号为2
          newX = tables[pa].x - wh[tables[pa].ceng].w / 2; //father.x-father.w/2
        }
        if (tables[i].locate == 3) { //节点序号为3
          newX = tables[pa].x; //father.x
        }
        if (tables[i].locate == 4) { //节点序号为4
          newX = tables[pa].x + wh[tables[pa].ceng].w / 2; //father.x+father.w/2
        }
        if (tables[i].locate == 5) { //节点序号为5
          //pa = tables[i].parents; //双亲的序号
          newX = tables[pa].x + wh[tables[pa].ceng].w; //father.x+father.w
        }
        break;

      default: //其他情况，给出出错信息
        break;
    }

    return newX;
  }

 // /**设置各个节点坐标(x,y)的值*/
 // void setXandY() {
  //  adjustWH(); //调整
  //  adjustWH(); //设置
 // }

  public void changePathQueue(ArrayQueue q){
    Object name=new Object();
    int num;
    for(int i=0;!q.isEmpty();i++){
      name = q.getFrontElement();
      num = search(name);
      path[i] = num;
      q.remove();
    }
  }
  public boolean isEmpty(){
     return tables[0]==null;
  }

  public void getPaintTableWH(int w,int h){
    paintTableWidth=w;
    paintTableHeight=h;
  }

  public void setWH(int w1){
    int wi=w1,hi=this.paintTableHeight/(treeCeng+1);//设定的w,h 的值
    //构造WH表
    for (int i = 1; i <= treeCeng; i++) {//第一层开始
      wh[i] = new WideHigh(wi,hi);
      //wh[i].setWH(w, h);
      wi = wi /2;
      hi = hi ;
    }

  }



}