本文實例講述了Java實現二叉樹的建立、計算高度與遞歸輸出操作。分享給大家供大家參考，具體如下：
1. 建立 遞歸輸出 計算高度 前中后三種非遞歸輸出
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"); }}希望本文所述對大家java程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
