/**

  *数据结构之树的实现

  *2016/4/29

  *

  **/

 package cn.Link;

 public class Tree {

     Node head = new Node();

     Tree(){} 

     //内部节点类

     class Node{

         String date;

         Node left;

         Node right;

         Node(){ }

         Node(String date){

             this.date = date;

             this.left = null;

             this.right = null;

         }

     }

     //给深度为n的满二叉树添加数据  n表示数的深度

     public void addTree(Node preNode,int n){

         if(n ==1) return;

         preNode.date = "sum"+n;

         Node preNodeLeft = new Node();

         Node preNodeRight = new Node();

         preNode.left = preNodeLeft;

         addTree(preNodeLeft,n-1);

         preNode.right = preNodeRight;

         addTree(preNodeRight,n-1);

     }

     //前序遍历二叉树  并输出

     public void printTreePre(Node preNode){

         if(preNode == null) return;

         if(preNode.left!=null || preNode.right!=null)

         System.out.print(preNode.date+"  ");

         printTreePre(preNode.left);

         printTreePre(preNode.right);

     }   

     //中序遍历二叉树  并输出

     public void printTreeAmong(Node preNode){

         if(preNode == null) return;

         printTreeAmong(preNode.left);

         if(preNode.left!=null || preNode.right!=null)

         System.out.print(preNode.date+"  ");

         printTreeAmong(preNode.right);

     }   

     //后序遍历二叉树  并输出

     public void printTreeRear(Node preNode){

         if(preNode == null) return;

         printTreeRear(preNode.left);

         printTreeRear(preNode.right);

         if(preNode.left!=null || preNode.right!=null)

         System.out.print(preNode.date+"  ");

     }   

     //测试函数

     public static void main(String [] args){

     Tree tree = new Tree();

     tree.addTree(tree.head,4);

     System.out.println("================前序遍历================");

     tree.printTreePre(tree.head);

     System.out.println();

     System.out.println("================中序遍历===============");

     tree.printTreeAmong(tree.head);

     System.out.println();

     System.out.println("================后序遍历===============");

     tree.printTreeRear(tree.head);

     System.out.println();

     System.out.println("============手工输出所有数据===========");

     System.out.println(tree.head.date);

     System.out.println(tree.head.left.date+" "+tree.head.right.date);

     System.out.println(tree.head.left.left.date+"  "+tree.head.left.right.date+"   "+tree.head.right.left.date+"   "+tree.head.right.right.date);

     }

 }