public class Tree_Link { private int save = 0; private int now = 0; Scanner sc = new Scanner(System.in); /* * 构造函数 */ Tree_Link(){ } /* * 链表建立 */ public Tree Link_Build(Tree head){// Tree head = new Tree();//头节点 System.out.println("继续code：1"); int flag = sc.nextInt(); if(flag != 1){ return head; }else{ System.out.println("/n/n/n输入 节点信息："); head.SetCode(sc.nextInt()); System.out.println("/n建立 左 子树code：1 否则：0"); flag = sc.nextInt(); if(flag == 1){ now++; Tree LTree = new Tree(); head.SetLtree(LTree); LTree.SetFronttree(head);//设置父母节点 Link_Build( head.GetLtree() ); } System.out.println("/n当前位置：" + head.GetCode()); System.out.println("/n建立 右 子树code：1 否则：0"); flag = sc.nextInt(); if(flag == 1){ now++; Tree Rtree = new Tree(); head.SetRtree(Rtree); Rtree.SetFronttree(head);//设置父母节点 Link_Build( head.GetRtree() ); } if( now > save ){ save = now; } now--; } return head; } /* * 输出树 */ public Tree output(Tree head){ int flag; if(head.GetCode() == -1){ return head; }else{ System.out.println("/n当前位置：" + head.GetCode()); System.out.println(head.GetLtree() != null); if(head.GetLtree() != null){ System.out.println("/n访问 左子树:"); output( head.GetLtree() ); } if(head.GetRtree() != null){ System.out.println("/n访问 右子树:"); output( head.GetRtree() ); } } return head; } /* * 获得高度 */ public int GetSave(){ return this.save; } /* * 非递归 前序遍历 */ public void Front_Traverse(Tree head){ Tree star = head;//退出标记 int choose = 1; //左 int flag = 1; //右 System.out.println( "<---前序遍历--->" + head.GetCode() );//先访问根 while(true){ if( head.GetLtree() != null && choose != 0 ){ head = head.GetLtree(); System.out.println( "<---前序遍历--->" + head.GetCode() );//获得信息 flag = 1; }else if( head.GetRtree() != null && flag != 0 ){ head = head.GetRtree(); System.out.println( "<---前序遍历--->" + head.GetCode() ); choose = 1; }else if( flag == 0 && choose == 0 && head == star){ break; }else{ if(head == head.GetFronttree().GetRtree()){ flag = 0; choose = 0; } if(head == head.GetFronttree().GetLtree()){ choose = 0; flag = 1; } head = head.GetFronttree(); System.out.println("获得 父母" + head.GetCode()); System.out.println( "/n/n/n" ); } } } /* * 非递归 中序遍历 */ public void Center_Traverse(Tree head){ Tree star = head;//退出标记 int choose = 1; //左 int flag = 1; //右 while(true){ if( head.GetLtree() != null && choose != 0 ){ head = head.GetLtree(); flag = 1; }else if( head.GetRtree() != null && flag != 0 ){ if(head.GetLtree() == null){//因为左边为空而返回 System.out.println( "<-1--中序遍历--->" + head.GetCode()); } head = head.GetRtree(); choose = 1; }else if( flag == 0 && choose == 0 && head == star){ break; }else{ int area = 0;//判断哪边回来 flag = 1; choose = 1; if(head == head.GetFronttree().GetRtree()){ area = 1;//右边回来 flag = 0; choose = 0; } if(head == head.GetFronttree().GetLtree()){ area = 2;//左边回来 choose = 0; flag = 1; } if( head.GetLtree() == null && head.GetRtree() == null ){//因为左边为空而返回 System.out.println( "<-2--中序遍历--->" + head.GetCode()); } head = head.GetFronttree(); if( area == 2){//因为左边访问完返回 System.out.println( "<-3--中序遍历--->" + head.GetCode()); } System.out.println("获得 父母" + head.GetCode()); System.out.println( "/n/n/n" ); } } } /* * 非递归 后续遍历 */ public void Bottom_Traverse(Tree head){ Tree star = head;//退出标记 int choose = 1; //左 int flag = 1; //右 while(true){ if( head.GetLtree() != null && choose != 0 ){ head = head.GetLtree(); flag = 1; }else if( head.GetRtree() != null && flag != 0 ){ head = head.GetRtree(); choose = 1; }else if( flag == 0 && choose == 0 && head == star){ break; }else{ int area = 0;//判断哪边回来 flag = 1; choose = 1; if(head == head.GetFronttree().GetRtree()){ area = 1;//右边回来 flag = 0; choose = 0; } if(head == head.GetFronttree().GetLtree()){ choose = 0; flag = 1; } if(head.GetRtree() == null){//因为右边为空而返回 System.out.println( "<-1--后序遍历--->" + head.GetCode()); } head = head.GetFronttree(); if( area == 1){ System.out.println( "<-2--后序遍历--->" + head.GetCode()); } System.out.println("获得 父母" + head.GetCode()); System.out.println( "/n/n/n" ); } } }}
2. Tree 类实现：
public class Tree { private int code = -1; private Tree Fonttree; private Tree Ltree; private Tree Rtree; Tree(){ this.code = -1; this.Ltree = null; this.Rtree = null; } /* * 树内容查看方法： */ public void SetCode(int code){//设置编号 this.code = code; } public int GetCode(){ //获取编号 return this.code; } /* * 设置父母指针： */ public void SetFronttree(Tree Front){ this.Fonttree = Front; } public Tree GetFronttree(){ System.out.println("获得 父母"); return this.Fonttree; } /* * 设置左子女： */ public void SetLtree(Tree Ltree){ this.Ltree = Ltree; } public Tree GetLtree(){ System.out.println("获得左子树"); return this.Ltree; } /* * 设置右子女： */ public void SetRtree(Tree Rtree){ this.Rtree = Rtree; } public Tree GetRtree(){ System.out.println("获得右子树"); return this.Rtree; }}
3. 主函数测试：
public class MainActivity { Scanner sc = new Scanner(System.in); public static void main(String[] args) { Tree head = new Tree(); Tree_Link link_1st = new Tree_Link(); head = link_1st.Link_Build(head); System.out.println("Build succeed !"); System.out.println("/n二叉树高度-->" + link_1st.GetSave()); link_1st.output(head); System.out.println("Output Over !"); System.out.println("/n/n<----------------前------------------>/n前序访问根："); link_1st.Front_Traverse(head); System.out.println("/n/n<----------------中------------------>/n中序访问根："); link_1st.Center_Traverse(head); System.out.println("/n/n<----------------后------------------>/n后序访问根："); link_1st.Bottom_Traverse(head); System.out.println("/n/n/n/nText over !/n/n/n"); }}
