table.java~46~

源程序（包括最初的版本

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.
 * @version 4.3(2005.7.12) 决定了摆放的方法节点的摆放的方法.标版!
 * @version 4.4(2005.7.12)
 */

import queue.*;

public class Table {
  protected TableNode tables[]; //数据元素
  protected int number; //节点个数
  protected int treeCeng; //树的高度
  protected WideHigh wh[]; //记录每层宽和高的数组
  protected int path[]; //存放树和二叉树遍历时的路径数组
  //protected int w0;//第一层的w,h
  protected int paintTableWidth, paintTableHeight; //画板的宽度和高度
  protected int r; //半径

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

  public Table(int number) {
    tables = new TableNode[number];
    path = new int[number];
    //w0=120;
    r = 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(120); ////输入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;
      }
    }

    adjustWH(120); //初始
  }

  /**计算并调整宽度和高度(w,h)的值
   * 用了辅助类WH,记录静态的宽度和高度
   * 该方法计算每个节点的坐标,然后进行调整
   * 每个节点的度数<=5
   *
   * 2005.7.5
   * 经用图形测试，发现节点的坐标的算法还是不太合理！！
   * 决定换一种思路
   * 前面一样的做法，当重叠或交叉时，改变他们父亲所在层的w,的值。
   * ！！！但是当2w放不下那么多的节点时，就把第一层的w放大，从新进行一边各个节点的x,y调整
   * 然后用图形学的缩放原理缩小在画布之内
   *
   *
   * */
  void adjustWH(int w0) {
    //if(w0>=400) return ;
    wh = new WideHigh[treeCeng + 1]; //宽和高的数组
    //int r=r; //节点的半径
    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(w0); //设置第一层的w,可调!!
    tables[0].setXY(x0, y0);
    i = 1;
    while (tables[i] != null) { //从第二个节点开始
      //if(tables[i].getX()>paintTableWidth/2||tables[i].getX()<(0-paintTableWidth/2)) return;

      //初步设定默认的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) { //重叠
          //wh[tables[pa].ceng].w >= 2 * r) {

          /****************************************************
           这段代码本是当w过小放不下过多的节点（即兄弟节点之间重叠了的时候）放大第一层的w的。
           但是发现放大后的效果不胜理想。
             if (wh[tables[pa].ceng].w <= 2 * r) {
             setWH(w0+=10); //放大第一层的w
             if(w0>=300) break;
               adjustWH(w0);
               break;
            }
           *****************************************************/

          {
            //调整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值
   * 注意，我这里只考虑了每个度数<=5的情况。*/
  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;
  }

  /**转换树与二叉树遍历时的节点路径，以path数组记录节点元素在表中的序号*/
  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 = paintTableHeight/3, hi = 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;
    }
  }

}