tree.java

源程序（包括最初的版本

package App;

/**
 * <p>Title: 树</p>
 * <p>Description: 无论是二叉树还是树，都改成了孩子兄弟链表的形式，故二叉树所画出的图形式样也会有所变化
 *                 需要的改进，1.由字符串输入时要有个判断字符串是否合格的判定语句</p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author liuli
 * @version 1.1(2005.6.29)
 */

import queue.*;

public class Tree {
  TreeNode root;// root为根结点的引用
  Table table;
  String s;

  public Tree() {}

  //类的操作方法
   /**判空，仅当空树返回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();
      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;//链接其他孩子节点
              }
          }
      }
  }

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


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

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

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

    //texteet
    Tree t=new Tree();
    t.init(s);
    System.out.println("树的先根遍历");
    t.preOrder();
    System.out.println("\n");
     System.out.println("树的后根遍历");
    t.postOrder();
    System.out.println("\n");
     System.out.println("造表");
    int i=0;
    while(t.table.tables [i]!=null){
      System.out.println(t.table.tables[i].toString());
      i++;
    }
     System.out.println("节点个数");
    System.out.println(t.table.number);


  }







}