linkedtree.java~1~

源程序（包括最初的版本

package tree;

/**
 *
 */

import queue.*;
import stack.*;
class LinkedTree implements Tree{
    ChildSiblingNode root;// root为根结点的引用
    static int count;// 结点计数器
    static int leaves;//叶子计数器

    public LinkedTree() {
    }

    //类的操作方法
    /**判空，仅当空树返回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 ChildSiblingNode(root,
                      ((LinkedTree) firstChild).root,
                      ((LinkedTree) nextSibling).root);
  }

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

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

  /**叶子计数*/
  public int leaf(){
      leaves=0;//叶子初始为0个
      thePreOrderLeaf(root);
      return leaves;//反回实际的叶子数
  }
  /**实际的叶子计数算法，先序*/
  static void thePreOrderLeaf(ChildSiblingNode t) {
      if(t!=null){
          if(t.firstChild==null) {//头小孩为空，则叶子数加1
               leaves++;
          }
          thePreOrderLeaf(t.firstChild);//遍历左小孩
          thePreOrderLeaf(t.nextSibling); //遍历右兄弟
      }
  }

  /**求树的深度*/
  public int height() {
      return theHeight(root);
  }
  /**实际的求树的深度算法，后序*/
  static int theHeight(ChildSiblingNode t) {
      if(t==null) return 0;//空节点返回0
      int hf=theHeight(t.firstChild );//遍历左小孩，获得左小孩的
      int hn=theHeight(t.nextSibling );//遍历右兄弟，获得右兄弟的树深
      if(hf+1>hn) return hf+1;//左小孩树深+1（即其双亲的树深)大于右兄弟的，则返回左小孩双亲的树深
      else return hn;//否则返回右兄弟的树深
  }

/**由二元组生成数*/
  public void creatTree(String s) {
      String  fa,ch; //双亲和孩子所表示的字符串
      int i=0;
      ChildSiblingNode p1;
      ChildSiblingNode p2;
      ChildSiblingNode 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 ChildSiblingNode(ch);//创建节点
          q.put(p1);//指针入队列
          if(fa.compareTo("#")==0) root=p1;//如果所建为根节点
          else {
              p2=(ChildSiblingNode)q.getFrontElement();//取队头元素
              while(!p2.element.equals(fa)) {//查询双亲节点
                  q.remove();
                  p2=(ChildSiblingNode)q.getFrontElement();
              }
              if(p2.firstChild==null) {
                  p2.firstChild=p1;  r=p1;//链接第一个孩子节点
              }
              else {
                  r.nextSibling=p1;r=p1;//链接其他孩子节点
              }
          }
      }
  }

  /**输出由根到叶子的所有路径*/
   public void outPath() {
       ArrayStack s=new ArrayStack();
       theOutPath(root,s);
   }
  /**实际的输出由根到叶子的所有路径算法*/
  void theOutPath(ChildSiblingNode t,ArrayStack s){
      while(t!=null) {
          s.push(t);//注意，入栈的是t,而不是老师给的算法中的t.element
          if(t.firstChild==null) //头小孩为空则输出一条路径
              System.out.println(s.toString());
          else theOutPath(t.firstChild,s);//否则递归
          t=(ChildSiblingNode)s.pop();
          t=t.nextSibling;
      }
  }

  /** 由树的双亲表示法建立树的孩子兄弟链表*/
   public void makeChildSiblingTree(ParentTree parentn){
       theMakeChildSiblingTree(root,parentn);
   }
   /**实际的由树的双亲表示法建立树的孩子兄弟链表算法*/
   void theMakeChildSiblingTree(ChildSiblingNode t,ParentTree parent){
      // ParentTree n=new ParentTree();
       ChildSiblingNode p1;
       ChildSiblingNode p2;
       ChildSiblingNode r=t;
       ArrayQueue q=new ArrayQueue();
       int i;
       for(i=0;i<parent.n;i++) {//当i>=节点个数时结束
           p1=new ChildSiblingNode(parent.node[i].element);//创建节点
           q.put(p1);//入队
           if(parent.node[i].parent==-1) { t=p1;root=t; }//如果是根节点
           else {
               p2=(ChildSiblingNode)q.getFrontElement();//取队头元素
               while(!p2.element.equals(parent.node[parent.node[i].parent].element)){//查询双亲节点
                   q.remove();
                   p2=(ChildSiblingNode)q.getFrontElement();
               }//循环结束后p2指向双亲节点
               if(p2.firstChild==null) {//头小孩为空
                   p2.firstChild=p1;  r=p1;//链接第一个孩子节点
               }
               else {//头小孩不为空
                   r.nextSibling=p1;r=p1;//链接其他孩子节点
               }
           }
       }
   }





  public static void main(String args[]) {

      // 用缺省构造方法生成八个空树的对象,称呼分别是Null,a,b,c,d,e,f,g,h,i,j,k。
      LinkedTree Null = new LinkedTree();
      LinkedTree a = new LinkedTree();
      LinkedTree b = new LinkedTree();
      LinkedTree c = new LinkedTree();
      LinkedTree d = new LinkedTree();
      LinkedTree e = new LinkedTree();
      LinkedTree f = new LinkedTree();
      LinkedTree g = new LinkedTree();
      LinkedTree h = new LinkedTree();
      LinkedTree i = new LinkedTree();
      LinkedTree j = new LinkedTree();
      LinkedTree k = new LinkedTree();
      //测试树的模型
      /**            1
       *          /  \  \
       *         2   3   4
       *        /\        \
       *       5  6        7
       *                    \
       *                     8
       *                   / \ \
       *                  9  10 11
       */
      k.makeTree(new Integer(11), Null, Null);
      j.makeTree(new Integer(10), Null, k);
      i.makeTree(new Integer(9), Null, j);
      h.makeTree(new Integer(8), i, Null);
      g.makeTree(new Integer(7), h, Null);
      f.makeTree(new Integer(6), Null, Null);
      e.makeTree(new Integer(5), Null, f);
      d.makeTree(new Integer(4), g, Null);
      c.makeTree(new Integer(3), Null, d);
      b.makeTree(new Integer(2), e, c);
      a.makeTree(new Integer(1), b, Null);

      /**测试先根算法preOrder()*/
      System.out.println("先根测试 ");
      System.out.println("Preorder tree is ");
      a.preOrder();
      System.out.println();

      /**测试先根算法preOrder()*/
      System.out.println("后根测试");
      System.out.println("Postorder tree is ");
      a.postOrder();
      System.out.println();

      /**测试叶子计数算法leaf()*/
      System.out.println("求叶子 ");
      System.out.println("the tree's leaves are " + a.leaf());

      /**测试树深算法heagth()*/
      System.out.println("求树深 ");
      System.out.println("the tree's heagth is " + a.height());

      /**测试由二元组生成数creatTree()*/
      System.out.println("二元组生成树 ");
      String s = "#AABACADCECF##";
      LinkedTree t=new LinkedTree();
      System.out.println(s);
      t.creatTree(s);
      System.out.println("Preorder tree is ");
      t.preOrder();
      System.out.println();

      /**测试输出树的所有路径outPath()*/
      System.out.println("树的所有路径 ");
      a.outPath();

      /**测试由树的双亲表示法建立树的孩子兄弟链表算法makeChildSiblingTree*/
      //System.out.printl("树的双亲表示法立树的孩子兄弟链表 ");
      System.out.println("树的双亲表示法立树的孩子兄弟链表 ");
      ParentTreeNode p[]=new ParentTreeNode[7];
      p[0]=new ParentTreeNode("A",-1);
      p[1]=new ParentTreeNode("B",0);
      p[2]=new ParentTreeNode("C",0);
      p[3]=new ParentTreeNode("D",0);
      p[4]=new ParentTreeNode("E",2);
      p[5]=new ParentTreeNode("F",2);
      p[6]=new ParentTreeNode("G",5);
      ParentTree tree=new ParentTree(p,0,7);
      LinkedTree linktree=new LinkedTree();
      linktree.makeChildSiblingTree(tree);
      linktree.preOrder();
      System.out.println();
    }
}