binarytree.java~3~

源程序（包括最初的版本

package treeandbtreedemo;

/**
 * <p>Title: </p>
 * <p>Description:二叉树 </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0（2005.7.6）
 * @version 2.2(2005.7.6)在基础架构中添加了二叉树类，把树和二叉树两种结构分开来做了
 */
import stack.*; //调用了栈的包，在遍序的非递归算法中使用了栈
import queue.*; //调用了队的包，在横向遍历时使用到了

public class BinaryTree {
  protected BinaryTreeNode root; // root为根结点的引用
  protected Table table;
  protected ArrayQueue path;
  // 类数据成员

  static int count; // 结点计数器

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

  /**返回二叉树树根*/
  public Object root()
      {return (root == null) ? null : root.element;}

  public void makeTree(Object root, Object left, Object right) {
    this.root = new BinaryTreeNode(root,
                                   ( (BinaryTree) left).root,
                                   ( (BinaryTree) right).root);
    //把Object对象left和right转换成LinkedBinaryTree，再取根root才得到引用
    //以符合 BinaryTreeNode(Object,BinaryTreeNode,BinaryTreeNoded)的定义
    //这里left和right可都是对象，而没用引用参数，面向用户时把引用作参数违背封装原则
  }

  /** 前序遍历 */
  // 面向接口的实现方法，没有参数。树根root是私有之物，不许随便碰人家
  public void preOrder() {
    thePreOrder(root);
    table.changePathQueue(path);
  }

  /** 实际的前序遍历方法 */
  // 实际是安排了两层：preOrder( )对外，thePreOrder(root);对内玩真的
  // 递归调用的方法仅是属于一个实例的方法，故使用了static属性修饰符（避免产生多实例的空间浪费）
  void thePreOrder(BinaryTreeNode t) {
    if (t != null) {
      path.put(t.element);
      //System.out.print(t.toString() + " "); // 访问树根
      thePreOrder(t.leftChild); // 遍历左子树
      thePreOrder(t.rightChild); // 遍历右子树
    }
  }

  /** 中序遍历 */
  //public void inOrder(Method visit)
  public void inOrder() {
    theInOrder(root);
    table.changePathQueue(path);
  }

  /** 实际的中序遍历方法 */
   void theInOrder(BinaryTreeNode t) {
    if (t != null) {
      theInOrder(t.leftChild); // 遍历左子树
      path.put(t.element);
      //System.out.print(t.toString() + " "); // 访问树根
      theInOrder(t.rightChild); // 遍历右子树
    }
  }

  /** 后序遍历 */
  public void postOrder() {
    thePostOrder(root);
    table.changePathQueue(path);
  }

  /** 实际的后序遍历方法 */
   void thePostOrder(BinaryTreeNode t) {
    if (t != null) {
      thePostOrder(t.leftChild); // 遍历左子树
      thePostOrder(t.rightChild); // 遍历右子树
      path.put(t.element);
      //System.out.print(t.toString() + " "); // 访问树根
    }
  }

  /**由三元组生成二叉链表*/
  public void creatBinaryTree(String s) {
    String fa, ch, flag;
    int i = 0;
    BinaryTreeNode p1;
    BinaryTreeNode p2;
    ArrayQueue q = new ArrayQueue();
    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)) { //当孩子为"#"时结束,每次循环读取一新三元组
      p1 = new BinaryTreeNode(ch); //创建节点
      q.put(p1); //指针入队列
      if (fa.compareTo("#") == 0) {
        root = p1; //如果所建为根节点
      }
      else {
        p2 = (BinaryTreeNode) q.getFrontElement(); //取队头元素
        while (!p2.element.equals(fa)) { //查询双亲节点
          q.remove();
          p2 = (BinaryTreeNode) q.getFrontElement();
        }
        if (flag.compareTo("L") == 0||flag.compareTo("l") == 0) { //标记为左小孩
          p2.leftChild = p1;
        }
        else if (flag.compareTo("R") == 0||flag.compareTo("r") == 0) { //标记为右小孩
          p2.rightChild = p1;
        }
      }
    }
    table.creatBinaryTreeTable(s);
  }

  public void init(String s){
    //前面因该还要检测一下s的合法性
    this.creatBinaryTree(s);
    this.table=new Table();
    this.table.creatBinaryTreeTable(s);
  }


  public static void main(String args[]){
    String s="#ALABLACRBDLBER##L";
    BinaryTree t=new BinaryTree();
    t.creatBinaryTree(s);
    t.preOrder();
    System.out.println("\n");
    t.inOrder();
    System.out.println("\n");
    t.postOrder();
    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++]);
   }

  }

}