linkedbinarytree.java~145~

源程序（包括最初的版本

     ///node=n;
     Ceng(BinaryTreeNode n, int f){
       node=n;
       flag=f;
     }
   }

   /**实际的横向遍历，调用了队*/
   void theLevelOrder(BinaryTreeNode t) {
     ArrayQueue q = new ArrayQueue();
     BinaryTreeNode p;
     Ceng ceng;
     int i=1;
     if (t != null) {
       p = t;
       ceng=new Ceng(p,i);
       q.put(ceng);
       while (!q.isEmpty() && p != null) {
         if (p.leftChild != null) { ceng=new Ceng(p.leftChild,++i);q.put(ceng); }//左孩子存在则入队,层次加1
         if (p.rightChild != null){
           if(p.leftChild==null) ceng=new Ceng(p.rightChild,++i);//左小孩不存在则右小孩的层次加1
           else ceng=new Ceng(p.rightChild,i);//左孩子存在则右小孩的层次不变
           q.put(ceng);
         } //右孩子入队
         if (!q.isEmpty()) { //队不空则出队
           ceng=(Ceng)q.remove(); //出队
           if(q.isEmpty()||ceng.flag<((Ceng)q.getFrontElement()).flag)
             System.out.println(ceng.node.toString());//如果出队的节点层次<队头的则输出后换行
           else
             System.out.print(ceng.node.toString()+" ");
           if (!q.isEmpty()){
             ceng=(Ceng)q.getFrontElement();
             p = (BinaryTreeNode)ceng.node; //p指向队头所示的节点
           }
         }
       }
     }
   }



   /**删除二叉树中每一个元素值为x的节点为根的子树*/
   public void deleteSubtree(Object x) {
     theDeleteSubtree(root,x);
   }

   /**实际的删除子树的方法，先序*/
   static void theDeleteSubtree(BinaryTreeNode t,Object x){
     if(t!=null) {
       if(t.leftChild!=null&&t.leftChild.element.equals(x)) {
           //左小孩不为空且元素值与x相等
           //注意要用equals()方法，而不能用 == 符号！
          t.leftChild=null;
          //当找到元素值为x的节点时，该节点的左小孩置为空
       }
       if(t.rightChild!=null&&t.rightChild.element.equals(x)){
         t.rightChild=null;
       }
       theDeleteSubtree(t.leftChild, x);//遍历左子树
       theDeleteSubtree(t.rightChild, x);//遍历右子树

     }
   }

   /**由三元组生成二叉链表*/
   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) {//标记为左小孩
            p2.leftChild = p1;
          }
          else if(flag.compareTo("R") == 0){//标记为右小孩
            p2.rightChild=p1;
          }
        }
      }
   }

   /**由二叉树的前序序列和中序序列建立二叉链表*/
   public void crtBT(Object pre[],Object ino[]){
     root=theCrtBT(root,pre,ino,0,0,pre.length);
   }
   /**查找方法*/
   static int search(Object a[],Object b) {
     for(int i=0;i<a.length;i++) {
       if (a[i].equals(b))return i;
     }
     return -1;
   }
   /**实际的由二叉树的前序序列和中序序列建立二叉链表算法*/
   static BinaryTreeNode theCrtBT(BinaryTreeNode t,Object pre[],Object ino[],int ps,int is,int n){
    if(n==0) t=null;
    else {
       int k=search(ino,pre[ps]);
       if(k==-1) t=null;
       else{
         t=new BinaryTreeNode();
         t.element=pre[ps];//在此处如果pre定义的为char型，则似乎不能赋值给t.element
         if(k==is) t.leftChild=null;
         else t.leftChild=theCrtBT(t.leftChild,pre,ino,ps+1,is,k-is);
         if(k==is+n-1) t.rightChild=null;
         else t.rightChild =theCrtBT(t.rightChild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);

       }

     }
     return t;
   }

   /**按树状打印二叉树*/
   public void printBTree(){
     thePrintBTree(root,0);
   }
   /**实际的按树状打印二叉树算法*/
   static void thePrintBTree(BinaryTreeNode t,int i) {
     if(t.rightChild!=null) {
       thePrintBTree(t.rightChild ,i+1);
     }
     for(int j=1;j<=i;j++) {//打印空格
       System.out.print("   ");
     }
     System.out.println(t.element.toString());
     if(t.leftChild !=null) {
       thePrintBTree(t.leftChild ,i+1);
     }
   }

   /** 测试程序 */
   public static void main(String args[])
   {
     // 用缺省构造方法生成四个空树的对象,称呼分别是Null、x、y和z。嘿，有个叫Null
     LinkedBinaryTree Null = new LinkedBinaryTree(),
                       x = new LinkedBinaryTree(),
                       y = new LinkedBinaryTree(),
                       z = new LinkedBinaryTree();


    // 反复运用makeTree方法实际地链接出一棵二叉树，
    // 作为测试遍历方法的数据模型：
    /**
     *             4
     *            / \
     *           3
     *          / \
     *         1   2
     */

     y.makeTree(new Integer(1), Null, Null);
     z.makeTree(new Integer(2), Null, Null);
     x.makeTree(new Integer(3), y, z);
     y.makeTree(new Integer(4), x, Null);

      //如果你要是想添一个创建树的算法，可以写在测试加载中，放到接口中就不好，
      //因为定义输入的字符串太个性化，与接口的简约明了原则不符


      // 测试各种方法
/*      System.out.println("Preorder sequence is ");
      y.preOrder(); //在OO的理念中，对根的引用是不能暴露在外的，即不应有参数了
                    //你能看出C算法的小家子气了吧，到人家随便的翻人的东西，像什么话呀
      System.out.println();
*/
/*
      System.out.println("Inorder sequence is ");
      y.inOrder();
      System.out.println();
*/
      System.out.println("Postorder sequence is ");
      y.postOrder();
      System.out.println();
/*
      System.out.println("Number of nodes = " + y.size());

      System.out.println("Height = " + y.height());
*/

      //测试两二叉树的相似Similar()
          /**
            *      4                  7
            *     / \                / \
            *    3                  6   8
            *   / \                / \
            *  1   2              4   5
            *                        /
            *                       9
           */

      LinkedBinaryTree Nullother = new LinkedBinaryTree(),//构造另一个二叉树
                      xother = new LinkedBinaryTree(),
                      yother = new LinkedBinaryTree(),
                      zother = new LinkedBinaryTree(),
                      mother=  new LinkedBinaryTree(),
                      nother= new LinkedBinaryTree();
      nother.makeTree(new Integer(9), Null, Null);
      yother.makeTree(new Integer(4), Null, Null);
      mother.makeTree(new Integer(8), Null, Null);
      zother.makeTree(new Integer(5), nother, mother);
      xother.makeTree(new Integer(6), yother,zother);
      yother.makeTree(new Integer(7), xother,mother);
      System.out.println("Preorder sequence is ");//先序打印第一个树
      y.preOrder();
      System.out.println();
      System.out.println("Other Preorder sequence is ");//先序打印第二个树
      yother.preOrder();
      System.out.println();

      int t=y.Similar(yother.root);//比较俩树是否相似，相似返回1，否则返回0
      if(t==1) System.out.println("two trees are similar");
      else System.out.println("two trees aren't similar");



      //测试先序的非递归算法preOrder_iter()
      System.out.println("Preorder_iter sequence is ");
      y.preOrder_iter();
      System.out.println();

      //测试后序的非递归算法postOrder_iter()
      System.out.println("Postorder_iter sequence is ");
      y.postOrder_iter();
      System.out.println();

     //测试横向遍历算法levelOrderTraverse()
      System.out.println("levelOrder sequence is ");
      yother.levelOrderTraverse();
      System.out.println();


     //测试删除元素值为x的节点为根的子树deleteSubtree()
      System.out.println("Preorder sequence is ");//显示删除前的
      y.preOrder();
      System.out.println();
      y.deleteSubtree(new Integer(3));//删除
      System.out.println("delete 3,the new Preorder sequence is ");//显示删除后的
      y.preOrder();
      System.out.println();


      //测试三元组成二叉树
      //String s="#ALABLACRBDLCLCFRDGRF##L";
      String s="#ALABLACRBDLCELCFRDGRFHL##L";
      LinkedBinaryTree tree=new LinkedBinaryTree();
      System.out.println(s);
      tree.creatBinaryTree(s);
      System.out.println("Preorder tree is ");
      tree.preOrder();
      System.out.println();

      //测试由先序序列和中序序列建立二叉链表
      Object pre[]={"a","b","c","d","e","f","g"};
      Object ino[]={"c","b","d","a","e","g","f"};
      LinkedBinaryTree treeother=new LinkedBinaryTree();
      //treeother.crtBT(pre,ino);
      ////treeother.crtBT(pre,ino);
      treeother.crtBT(pre,ino);
      //System.out.println("Preorder tree is ");
      System.out.println("Preorder tree is ");
      treeother.preOrder();//先序打印
      //System.out.println();
      //System.out.println();
      System.out.println();
      System.out.println("Inorder tree is ");
      treeother.inOrder();//中序打印
      System.out.println();
      System.out.println("Postorder tree is ");
      treeother.postOrder();//后序打印
      System.out.println();

      //测试按树状打印二叉树printBTree()
      yother.printBTree();

 }
}