treepersongroup.java

本软件是使用java 开发的

package datastructure;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2004</p>
 * <p>Company: </p>
 * @author unascribed
 * @version 1.0
 */

import java.awt.*;

class TreePersonGroup {
  private CodeAnimationPanel codePanel;

  private TreePerson treeArray[];
  TreeStack theStack;
  private int filledNodes;
  private String note = null;
  private boolean isRand;
  private int value;
  private int codePart;
  private int opMode;
  private int curIn;
  private int curInOld;
  private int oldArrow;
  private int visitArray[];
  private int visitIndex;
  private int successor;
  private boolean drawAll;
  private int drawMode;
  private boolean doneFlag = false;
  private int p;

  public TreePersonGroup(CodeAnimationPanel code) {
    this.codePanel = code;

    isRand = true;
    codePart = 1;
    drawMode = 2;
    treeArray = new TreePerson[64];
    for (int i = 0; i < 64; i++)
      treeArray[i] = null;

    filledNodes = 0;
    note = "按新建开始";
    visitArray = new int[64];
    visitIndex = 0;
    theStack = new TreeStack();
  }

  public TreePerson makePerson(int i) { //生成一个节点
    int j = 100 + (int) (Math.random() * 154);
    int k = 100 + (int) (Math.random() * 154);
    int l = 100 + (int) (Math.random() * 154);
    Color color = new Color(j, k, l);
    return new TreePerson(i, color);
  }

  public void setDrawAll(boolean flag) {
    drawAll = flag;
  }

  public void fill(boolean flag, int i) {

    doFill(i);
    drawMode = 2;
    note = "生成" + i + "个节点的树";
    oldArrow = curInOld;
    curInOld = 0;
    codePart = 1;
    return;

  }

  public void doFill(int i) {
    int j = 0;
    for (int l = 0; l < 64; l++)
      treeArray[l] = null;

    filledNodes = 0;
    boolean aflag[] = new boolean[100];
    for (int i1 = 0; i1 < 100; i1++) //用来控制不出现重复的节点
      aflag[i1] = false;

    while (filledNodes < i && j < 100) { //生成的节点数小于要求的节点数则循环
      int k;
      do
        k = (int) (Math.random() * 99); //随机生成节点直
      while (aflag[k]); //已经有了的节点则aflag[k]直为true,while直到aflag[k]为false才退出
      TreePerson TreePerson1 = makePerson(k);
      curIn = 0; //从根节点开始
      do {
        if (curIn > 30) {
          j++;
          break;
        }
        if (treeArray[curIn] == null) {
          treeArray[curIn] = TreePerson1;
          filledNodes++;
          aflag[k] = true;
          break;
        }
        if (k < treeArray[curIn].getHeight()) //为了生成根节点大于左孩子小于右孩子
          curIn = 2 * curIn + 1;
        else
          curIn = 2 * curIn + 2;
      }
      while (true);
    }
  }

  public void setBegin(boolean flag) { //设置doneFlag
    doneFlag = flag;
  }

  public boolean isOver() { //判断是否运行结束
    return doneFlag;
  }

  public int[] getStack() { //获得栈中的数据
    int a[] = new int[20];
    int i = 0;

    while (i <= theStack.top) {
      try {
        if (theStack.st[i] > 30 || treeArray[theStack.st[i]] == null) {
          i++;
          continue;
        }

        a[i] = treeArray[theStack.st[i]].getHeight();
        i++;
      }
      catch (Exception e) {
        System.out.println("theStack.top=" + theStack.top);
        System.out.println("theStack.st[i]   " + theStack.st[i]);
      }
    }
    return a;
  }

  public void setDrawMode(int mode) { //设置是画全部还是部分
    drawMode = mode;
  }

  public int getTop() {
    return theStack.getTop();
  }

  public void traverse() {
    switch (codePart) {
      case 1:

        if (doneFlag)
          return;
        visitIndex = 0;
        note = "先序遍历这树 ";
        curIn = 0;
        oldArrow = curInOld;
        curInOld = 0;
        drawMode = 0;
        codePart = 3;
        p = 0;
        codePanel.highlight(1);
        return;
      case 3:
        theStack.push(0);
        codePanel.highlight(3);
        note = "初始化栈和压入根节点";
        codePart = 4;
        return;
      case 4:
        if (!theStack.isEmpty()) {
          note = "栈不为空";
          oldArrow = curInOld;
          curIn = theStack.st[getTop()];
          curInOld = curIn;
          oldArrow = curInOld;
          codePart = 6;
        }
        else {
          codePart = 14;
        }
        codePanel.highlight(4);

        return;
      case 6:

        oldArrow = curInOld;
        curIn = theStack.st[getTop()];
        curInOld = curIn;

        if (treeArray[curIn] != null) {
          codePart = 7;
        }
        else
          codePart = 9;
        codePanel.highlight(6);
        return;
      case 7:

        visitArray[visitIndex] = treeArray[theStack.st[getTop()]].getHeight();
        treeArray[theStack.st[getTop()]].setColor(Color.gray);
        visitIndex++;

        note = "访问" + treeArray[theStack.st[getTop()]].getHeight();
        codePart = 8;
        codePanel.highlight(7);
        return;
      case 8:

        theStack.push(2 * curIn + 1);
        note = "压入左孩子";
        codePart = 6;
        codePanel.highlight(8);
        return;
      case 9:
        p = theStack.pop();
        note = "弹出空节点";
        codePart = 10;
        codePanel.highlight(9);
        return;
      case 10:
        if (!theStack.isEmpty()) {
          codePart = 11;
          note = "栈不为空";
        }
        else {
          codePart = 4;

        }
        codePanel.highlight(10);
        return;
      case 11:
        curIn = theStack.pop();
        note = "出栈";
        codePart = 12;
        codePanel.highlight(11);
        return;
      case 12:
        theStack.push(2 * curIn + 2);
        note = "压入右孩子";
        codePart = 4;
        codePanel.highlight(12);
        return;
      case 14:
        codePanel.highlight(14);
        note = "运行结束";
        doneFlag = true;

    }
  }

  //绘制一个节点
  public void drawOneNode(Graphics g, int i) {
    if (treeArray[i] == null)
      return;
    int j = treeArray[i].getHeight();
    Color color = treeArray[i].getColor();
    int k = i % 2;
    int l = 15;
    byte byte0 = 0;
    int i1 = -1;
    if (i > 0 && i < 3) { //一二层
      l = 7 + (i - 1) * 16;
      byte0 = 1;
      i1 = k != 1 ? l - 8 : l + 8;
    }
    else
    if (i > 2 && i < 7) { //三层
      l = 3 + (i - 3) * 8;
      byte0 = 2;
      i1 = k != 1 ? l - 4 : l + 4;
    }
    else
    if (i > 6 && i < 15) { //四层
      l = 1 + (i - 7) * 4;
      byte0 = 3;
      i1 = k != 1 ? l - 2 : l + 2;
    }
    else
    if (i > 14 && i < 31) { //五层
      l = (i - 15) * 2;
      byte0 = 4;
      i1 = k != 1 ? l - 1 : l + 1;
    }
    int j1 = 10 + (l * 26) / 2;
    int k1 = 70 + byte0 * 40;
    int l1 = 10 + (i1 * 26) / 2;
    int i2 = 70 + (byte0 - 1) * 40;
    if (byte0 > 0) {
      g.setColor(Color.black);
      g.drawLine(j1 + 10, k1 + 10, l1 + 10, i2 + 10);

    }
    g.setColor(color);
    g.fillOval(j1, k1, 20, 20);
    g.setColor(Color.black);
    g.drawOval(j1, k1, 20, 20);
    if (j < 10) {
      g.drawString(String.valueOf(j), j1 + 7, (k1 + 20) - 5);
      return;
    }
    else {
      g.drawString(String.valueOf(j), j1 + 4, (k1 + 20) - 5);
      return;
    }
  }

  //绘制所有节点和键头
  public void draw(Graphics g) {
    //根据绘制方式用不同的

    switch (drawMode) {
      case 0: //画改变的部分
        break;
      case 2: //画所有的
        g.setColor(Color.lightGray);
        g.fillRect(0, 0, 440, 300);
        for (int k = 30; k >= 0; k--)
          drawOneNode(g, k);
        break;
    }
    g.setColor(Color.lightGray);
    g.fillRect(10, 45, 200, 25);
    g.setColor(Color.black);
    g.drawString(note, 16, 64);
    g.setColor(Color.lightGray);
    g.fillRect(10, 280, 430, 25);
    g.setColor(Color.black);
    String s = "";
    for (int l = 0; l < visitIndex; l++)
      s = s + visitArray[l] + " ";

    g.drawString("访问序列" + s, 16, 296);
    drawOneNode(g, oldArrow);
    drawArrow(g, oldArrow, false);
    drawArrow(g, curInOld, true);

    drawMode = 2;
  }

//画箭头
  public void drawArrow(Graphics g, int i, boolean flag) {
    if (treeArray[i] == null)
      return;
    int j = 15;
    byte byte0 = 0;
    if (i > 0 && i < 3) { //用i来确定其坐标  一二层
      j = 7 + (i - 1) * 16;
      byte0 = 1;
    }
    else
    if (i > 2 && i < 7) { //三层
      j = 3 + (i - 3) * 8;
      byte0 = 2;
    }
    else
    if (i > 6 && i < 15) { //四层
      j = 1 + (i - 7) * 4;
      byte0 = 3;
    }
    else
    if (i > 14 && i < 31) { //五层
      j = (i - 15) * 2;
      byte0 = 4;
    }
    int k = 10 + (j * 26) / 2;
    int l = 70 + byte0 * 40;
    if (flag)
      g.setColor(Color.red); //用红色来画箭头
    else
      g.setColor(Color.lightGray); //用背景色画替代前一个箭头，既是删除上一个箭头
    int i1 = k + 10;
    int j1 = l - 2;
    byte byte1 = 20;
    g.drawLine(i1, j1, i1, j1 - byte1);
    g.drawLine(i1 - 1, j1, i1 - 1, j1 - byte1);
    g.drawLine(i1, j1, i1 - 3, j1 - 6);
    g.drawLine(i1 - 1, j1, i1 - 4, j1 - 6);
    g.drawLine(i1, j1, i1 + 3, j1 - 6);
    g.drawLine(i1 - 1, j1, i1 + 2, j1 - 6);
  }

}