tree.java~1~

源程序（包括最初的版本

package App;

/**
 * <p>Title: 树</p>
 * <p>Description: 无论是二叉树还是树，都改成了孩子兄弟链表的形式，故二叉树所画出的图形式样也会有所变化</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为根结点的引用

  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 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="#AABBDBE##";
    Tree t=new Tree();
    t.creatTree(s);
    t.preOrder();
    System.out.println("\n");
    t.postOrder();
  }







}