tree.java

源程序（包括最初的版本

package treeandbtreedemo;

/**
 * <p>Title: 树</p>
 * <p>Description: 无论是二叉树还是树，都改成了孩子兄弟链表的形式，故二叉树所画出的图形式样也会有所变化
 *                 需要的改进，1.由字符串输入时要有个判断字符串是否合格的判定语句</p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author liuli
 * @version 2.0(2005.7.3)加入图形界面!
 * @version 2.1(2005.7.5)初步加入动画和线程,产生节点的遍历动画效果
 * @version 2.2(2005.7.6)在基础架构中添加了二叉树类，把树和二叉树两种结构分开来做了
 */

import queue.*;

public class Tree {
  protected TreeNode root;// root为根结点的引用
  //protected Table table;
  protected ArrayQueue path;
  protected boolean creatSuccess=true;
  //String s;

  public Tree() {
    //table=new Table();
    path=new ArrayQueue();
  }

  //类的操作方法
   /**判空，仅当空树返回true */
  public boolean isEmpty() {
      return root == null;
  }

  /** @树不空返回根元素
    * @空树则返回空 */
  public Object root() {
      return (root == null) ? null : root.element;
  }

  /** 通过给定的根数据和孩子兄弟子树构造树*/
  public void makeTree(Object root, Object firstChild ,Object nextSibling){
      this.root = new TreeNode(root,
                      ((Tree) firstChild).root,
                      ((Tree) nextSibling).root);
  }

  /**由二元组生成树
   * 如  "#AABACADBEBFCGDHDI##"
   *                A
   *              / | \
   *             B  C  D
   *            /\  |  /\
   *           E  F G H  I
   *  要求字符串保持一定的次序输入
   **/
  public void creatTree(String s) {
      String  fa,ch; //双亲和孩子所表示的字符串
      int i=0;
      TreeNode p1;
      TreeNode p2;
      TreeNode r=root;
      ArrayQueue q=new ArrayQueue();
      try {
        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)) { //当孩子为"#"时结束
          //每次循环读取一对二元组
          p1 = new TreeNode(ch); //创建节点
          q.put(p1); //指针入队列
          if (fa.compareTo("#") == 0)
            root = p1; //如果所建为根节点
          else {
            p2 = (TreeNode) q.getFrontElement(); //取队头元素
            while (!p2.element.equals(fa)) { //查询双亲节点
              q.remove();
              p2 = (TreeNode) q.getFrontElement();
            }
            if (p2.firstChild == null) {
              p2.firstChild = p1;
              r = p1; //链接第一个孩子节点
            }
            else {
              r.nextSibling = p1;
              r = p1; //链接其他孩子节点
            }
          }
        }
      }
     catch (Exception ex) {
       creatSuccess=false;
     }

      //table.creatTreeTable(s);
  }

  /**初始化*/
  public void init(String s){
    //前面因该还要检测一下s的合法性
    this.creatTree(s);
    //this.table=new Table();
    //this.table.creatTreeTable(s);
  }


  /**先根遍历树*/
  public ArrayQueue preOrder() {
      thePreOrder(root);
      return path;
   }
  /**实际的先根遍历算法,二叉树的先序*/
  void thePreOrder(TreeNode t){
      if(t!=null) {
          //System.out.print(t.toString()+ " ");  // 访问树根
          path.put(t.element);
          thePreOrder(t.firstChild);             // 遍历左孩子树
          thePreOrder(t.nextSibling);            // 遍历右兄弟子树
      }
  }

  /**后根遍历树*/
  public ArrayQueue postOrder(){
      thePostOrder(root);
      return path;
  }
  /**实际的后根遍历算法，二叉树的中序*/
  void thePostOrder(TreeNode t){
      if(t!=null) {
          thePostOrder(t.firstChild);             // 遍历左孩子树
          //System.out.print(t.toString()+ " ");    // 访问树根
          path.put(t.element);
          thePostOrder(t.nextSibling);            // 遍历右兄弟子树
      }
  }



  //测试方法
/* public static void main(String args[]){
    //测造树和造表
    String s="#aabacadbebfbgchcicjdkdldmeneoepfqfrfs##";
        //"#AABACADBEBFCGDHDIDJHKHLHMINIOIPMQMRMSNTNUNV##";
        //"#AABACADBEBFCGDHDIDJHKHLHMINIOIPMQMRMSNTNUNV##";//MQMRMSNTNUNV
    //#01020304051a1b1c1d1e2a2b2c2d2e3a3b3c3d3e4a4b4c4d4e5a5b5c5d5e##

    //texteet
    Tree t=new Tree();
    t.init(s);
    t.preOrder();
    System.out.println("\n");
    t.postOrder();
    System.out.println("\n");
    int i=0;
    while(t.table.tables [i]!=null){
      System.out.println(i+"  "+t.table.tables[i].toString());
      i++;
    }
    System.out.println(t.table.number);

    t.preOrder();
    i=0;
    while(t.table.tables [i]!=null){
      System.out.println(t.table.path[i++]);
    }

  }
*/






}