//******************************************************************************************************//
//*****本程序包括簡(jiǎn)單的二叉樹類的實(shí)現(xiàn)和前序,中序,后序,層次遍歷二叉樹算法,*******//
//******以及確定二叉樹的高度,制定對(duì)象在樹中的所處層次以及將樹中的左右***********//
//******孩子節(jié)點(diǎn)對(duì)換位置,返回葉子節(jié)點(diǎn)個(gè)數(shù)刪除葉子節(jié)點(diǎn),并輸出所刪除的葉子節(jié)點(diǎn)**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //數(shù)據(jù)元數(shù)
private BinTree left,right; //指向左,右孩子結(jié)點(diǎn)的鏈
BinTree []elements = new BinTree[MAX];//層次遍歷時(shí)保存各個(gè)節(jié)點(diǎn)
    int front;//層次遍歷時(shí)隊(duì)首
    int rear;//層次遍歷時(shí)隊(duì)尾
private Object data; //數(shù)據(jù)元數(shù)
private BinTree left,right; //指向左,右孩子結(jié)點(diǎn)的鏈

public BinTree()
{
}
public BinTree(Object data)
{ //構(gòu)造有值結(jié)點(diǎn)
   this.data = data;
   left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //構(gòu)造有值結(jié)點(diǎn)
   this.data = data;
   this.left = left;
   this.right = right;
}
public String toString()
{
   return data.toString();
}

//前序遍歷二叉樹
public static void preOrder(BinTree parent){ 
     if(parent == null)
      return;
     System.out.print(parent.data+" ");
     preOrder(parent.left);
     preOrder(parent.right);
}

//中序遍歷二叉樹
public void inOrder(BinTree parent){
   if(parent == null)
      return;
   inOrder(parent.left);
   System.out.print(parent.data+" ");
     inOrder(parent.right);
}

//后序遍歷二叉樹
public void postOrder(BinTree parent){
   if(parent == null)
    return;
   postOrder(parent.left);
   postOrder(parent.right);
   System.out.print(parent.data+" ");
}

// 層次遍歷二叉樹 
public void LayerOrder(BinTree parent)
{ 
     elements[0]=parent;
     front=0;rear=1;
   while(front<rear)
   {
    try
    {
        if(elements[front].data!=null)
        {
           System.out.print(elements[front].data + " ");
           if(elements[front].left!=null)
          elements[rear++]=elements[front].left;
           if(elements[front].right!=null)
          elements[rear++]=elements[front].right;
           front++;
        }
    }catch(Exception e){break;}
   }
}

//返回樹的葉節(jié)點(diǎn)個(gè)數(shù)
public int leaves()
{
   if(this == null)
    return 0;
   if(left == null&&right == null)
    return 1;
   return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}

//結(jié)果返回樹的高度
public int height()
{
   int heightOfTree;
   if(this == null)
    return -1;
   int leftHeight = (left == null ? 0 : left.height());
   int rightHeight = (right == null ? 0 : right.height());
   heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight;
   return 1 + heightOfTree;
}

//如果對(duì)象不在樹中,結(jié)果返回-1;否則結(jié)果返回該對(duì)象在樹中所處的層次,規(guī)定根節(jié)點(diǎn)為第一層
public int level(Object object)
{
   int levelInTree;
   if(this == null)
    return -1;
   if(object == data)
    return 1;//規(guī)定根節(jié)點(diǎn)為第一層
   int leftLevel = (left == null?-1:left.level(object));
   int rightLevel = (right == null?-1:right.level(object));
   if(leftLevel<0&&rightLevel<0)
    return -1;
   levelInTree = leftLevel<rightLevel?rightLevel:leftLevel;
   return 1+levelInTree;
  
}

//將樹中的每個(gè)節(jié)點(diǎn)的孩子對(duì)換位置
public void reflect()
{
   if(this == null)
    return;
   if(left != null)
    left.reflect();
   if(right != null)
    right.reflect();
   BinTree temp = left;
   left = right;
   right = temp;
}

// 將樹中的所有節(jié)點(diǎn)移走,并輸出移走的節(jié)點(diǎn)
public void defoliate()
{
   if(this == null)
    return;
   //若本節(jié)點(diǎn)是葉節(jié)點(diǎn)，則將其移走
   if(left==null&&right == null)
   {
    System.out.print(this + " ");
    data = null;
    return;
   }
   //移走左子樹若其存在
   if(left!=null){
    left.defoliate();
    left = null;
   }
   //移走本節(jié)點(diǎn)，放在中間表示中跟移走...
   data = null;
   //移走右子樹若其存在
   if(right!=null){
    right.defoliate();
    right = null;
   }
}

   /**
* @param args
*/
public static void main(String[] args) {
   // TODO Auto-generated method stub
   BinTree e = new BinTree("E");
   BinTree g = new BinTree("G");
   BinTree h = new BinTree("H");
   BinTree i = new BinTree("I");
   BinTree d = new BinTree("D",null,g);
  
   BinTree f = new BinTree("F",h,i);
   BinTree b = new BinTree("B",d,e);
   BinTree c = new BinTree("C",f,null);

   BinTree tree = new BinTree("A",b,c);
  
        System.out.println("前序遍歷二叉樹結(jié)果: ");
        tree.preOrder(tree);
        System.out.println();
        System.out.println("中序遍歷二叉樹結(jié)果: ");
        tree.inOrder(tree);
        System.out.println();
        System.out.println("后序遍歷二叉樹結(jié)果: ");
        tree.postOrder(tree);
        System.out.println();
      System.out.println("層次遍歷二叉樹結(jié)果: ");
     tree.LayerOrder(tree);
     System.out.println();
        System.out.println("F所在的層次: "+tree.level("F"));
        System.out.println("這棵二叉樹的高度: "+tree.height());
         System.out.println("--------------------------------------");
         tree.reflect();
          System.out.println("交換每個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)后......");
          System.out.println("前序遍歷二叉樹結(jié)果: ");
        tree.preOrder(tree);
        System.out.println();
        System.out.println("中序遍歷二叉樹結(jié)果: ");
        tree.inOrder(tree);
        System.out.println();
        System.out.println("后序遍歷二叉樹結(jié)果: ");
        tree.postOrder(tree);
        System.out.println();
      System.out.println("層次遍歷二叉樹結(jié)果: ");
     tree.LayerOrder(tree);
     System.out.println();
        System.out.println("F所在的層次: "+tree.level("F"));
        System.out.println("這棵二叉樹的高度: "+tree.height());
}