linkedbinarytree.java~140~

源程序（包括最初的版本

/** 二叉链表类实现二叉树 */

package datastructures;
// 我都用了一个包名，为了测试方便


import stack.*;//调用了栈的包，在遍序的非递归算法中使用了栈
import queue.*;//调用了队的包，在横向遍历时使用到了

public class LinkedBinaryTree implements BinaryTree
{
   // 数据成员
   public BinaryTreeNode root;  // root为根结点的引用

   // 类数据成员

   static int count;         // 结点计数器

   // 你想想，再安排点啥属性，身高啊，体重啊，血型、皮肤颜色什么的

   // 类的操作方法

   /** @仅当空树返回true */
   public boolean isEmpty()
      {return root == null;}


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

   /** 通过给定的根和左右子数构造树
     * 注意: 并非是克隆,而是通过引用来链接 */
   public void makeTree(Object root, Object left, Object right)
   {
      this.root = new BinaryTreeNode(root,
                      ((LinkedBinaryTree) left).root,
                      ((LinkedBinaryTree) right).root);
      //把Object对象left和right转换成LinkedBinaryTree，再取根root才得到引用
      //以符合 BinaryTreeNode(Object,BinaryTreeNode,BinaryTreeNoded)的定义
      //这里left和right可都是对象，而没用引用参数，面向用户时把引用作参数违背封装原则
   }

   /** 删除左子树
     * @空树时抛出非法参数异常
     * @返回被删除的左子树 */
   public BinaryTree removeLeftSubtree()
   {
      if (root == null)
         throw new IllegalArgumentException("tree is empty");

      // 分离左子树并以leftSubtree给出
      LinkedBinaryTree leftSubtree = new LinkedBinaryTree();
      leftSubtree.root = root.leftChild;
      root.leftChild = null;

      return (BinaryTree) leftSubtree;
   }

   /** 删除右子树
     * @空树时抛出非法参数异常
     * @返回被删除的右子树 */
   public BinaryTree removeRightSubtree()
   {
      if (root == null)
         throw new IllegalArgumentException("tree is empty");

      // 分离右子树并以rightSubtree给出
      LinkedBinaryTree rightSubtree = new LinkedBinaryTree();
      rightSubtree.root = root.rightChild;
      root.rightChild = null;

      return (BinaryTree) rightSubtree;
   }

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

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

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

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


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

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

   /** 结点计数器方法 */
   public int size()
   {
      count = 0;
      thePreOrderCount(root);
      return count;
   }

   /** 实际的结点计数器方法 */
   static void thePreOrderCount(BinaryTreeNode t)
     {
        if (t != null)
        {
           count++;                                  // 逢结点记数+1
           thePreOrderCount(t.leftChild);            // 遍历左子树
           thePreOrderCount(t.rightChild);           // 遍历右子树
        }
   }

   /** @返回树深 */
   public int height()
      {return theHeight(root);}

   /** @返回以t为根的子树深 */
  static int theHeight(BinaryTreeNode t)
  {
      if (t == null) return 0;
      int hl = theHeight(t.leftChild);  // 左子树的树深
      int hr = theHeight(t.rightChild); // 右子树的树深
      if (hl > hr) return ++hl;
      else return ++hr;
   }

   /**判断两个二叉树是否相似*/
   public int Similar(BinaryTreeNode bRoot){
     return thePostOrderSimilar(root,bRoot);

   }

   /**实际的判断两个二叉树是否相似,后序*/
   static int thePostOrderSimilar(BinaryTreeNode b1,BinaryTreeNode b2){
     if(b1==null&&b2==null)
       return 1;//b1，b2节点都为空
     if((b1!=null&&b2==null)||(b1==null&&b2!=null))
       return 0;// b1，b2节点不全为空

     int t1=thePostOrderSimilar(b1.leftChild,b2.leftChild); //遍历左小孩，返回是否相似，1相似，0不相似
     int t2=thePostOrderSimilar(b1.rightChild,b2.rightChild); //遍历有小孩 ，返回是否相似
     return t1*t2; //只有在左右小孩都相似时才返回1
   }

   /** 先序遍历,非递归算法，使用了栈 */
   public void preOrder_iter(){
     thePreOrder_iter(root);
   }

   /**实际的先序遍历,非递归算法*/
   void thePreOrder_iter(BinaryTreeNode t) {
     if(t!=null) {
       BinaryTreeNode p=t;//p指向t
       ArrayStack s=new ArrayStack();//初始一个栈
       do {
         while(p!=null) {
           System.out.print(p.toString()+ " ");//对节点的操作
           s.push(p); p=p.leftChild;//不断进栈并向左小孩移动
         }
         if(!s.empty()) {
           p=(BinaryTreeNode)s.pop(); p=p.rightChild;//栈不空则退栈且向小右孩跨一步
         }
       }while(p!=null||!s.empty());//注意该约束条件，任意一个不空则继续进行
     }
   }

   /**自己做的实际的前序遍历,非递归算法.
    * 与老师的最主要不同是:老师的是不断进栈向左小孩移动，当节点为空且栈不空则退栈且向右小孩跨一步
    * 而自己做的是每次指针的移动都判断一下当前指针所指节点是否为空，不为空则向左小孩走一步，为空则。。。。。。
    * */
  /* public void thePreOrder_iter(BinaryTreeNode t) {

       BinaryTreeNode p = t; //p指向t
       ArrayStack s = new ArrayStack(); //初始一个栈
     do{
       if(p!=null) {
         System.out.print(p.toString()+ " ");
         s.push(p);p=p.leftChild;
       }
       else if(!s.empty()){
         p=( BinaryTreeNode)s.pop();
         p=p.rightChild;
       }
     }while(p!=null||!s.empty());
   }*/


   /** 后序遍历,非递归算法 */
   public void postOrder_iter() {
     thePostOrder_iter(root);
   }
   /**定义了一个内部类，它包括节点和一个标志域flag*/
   class BTreeNodeFlag {
     BinaryTreeNode node;
     int flag=0;//没有进行标志时的状态
     BTreeNodeFlag() {};
     BTreeNodeFlag(BinaryTreeNode tp) {node=tp;}
     BTreeNodeFlag(BinaryTreeNode tp,int f){node=tp;flag=f;}
   }
   /**实际的后序遍历,非递归算法，使用了栈和内部类BTreeNodeFlag*/
   void thePostOrder_iter(BinaryTreeNode t) {
     if(t!=null) {
       BinaryTreeNode p=t;//p指向t
       BTreeNodeFlag element;
       ArrayStack s=new ArrayStack();//初始一个栈
     do{
       while(p!=null) {//p节点不为空
          element = new BTreeNodeFlag();
          element.flag = 1; //标记为1
          element.node = p;
          s.push(element); //进栈
          p = p.leftChild; //p指向其左小孩

       }
       if(!s.empty()) {//栈不空
         element = (BTreeNodeFlag) s.peek();//获得栈顶元素
         if (element.flag == 2 && !s.empty()) { //栈顶元素标志域为 2且栈不空
           System.out.print(element.node.toString() + " ");//打印栈顶
           s.pop();//退栈
          if(!s.empty()){
            element = (BTreeNodeFlag) s.peek(); //获得新的栈顶元素
            if (element.flag == 1) { //该新的栈顶元素标志为1
              p = element.node.rightChild; //指向该栈顶元素所在德左节点
              element.flag = 2; //栈顶元素标志域为 2
            }
          }
         }
         else {
           element.flag = 2;
           p = element.node.rightChild;//p指向右小孩
         }
       }
       }while(p!=null||!s.empty());
     }
   }

   /**横向遍历，调用了队*/
   public void levelOrderTraverse() {
     theLevelOrder(root);
   }

   /**内部类，使用它表现层次关系*/
    class Ceng {
     BinaryTreeNode node;
     int flag;
     Ceng() {};
     //Ceng(BinaryTreeNode n, int ){
     ///node=n;