Java實(shí)現(xiàn)二叉樹(shù)的建立、計(jì)算高度與遞歸輸出操作示例
更新時(shí)間：2019年03月13日 11:30:00 作者：水中魚(yú)之1999
這篇文章主要介紹了Java實(shí)現(xiàn)二叉樹(shù)的建立、計(jì)算高度與遞歸輸出操作,結(jié)合實(shí)例形式分析了Java二叉樹(shù)的創(chuàng)建、遍歷、計(jì)算等相關(guān)算法實(shí)現(xiàn)技巧,需要的朋友可以參考下
本文實(shí)例講述了Java實(shí)現(xiàn)二叉樹(shù)的建立、計(jì)算高度與遞歸輸出操作。分享給大家供大家參考，具體如下：
1. 建立 遞歸輸出 計(jì)算高度 前中后三種非遞歸輸出
public class Tree_Link {
private int save = 0;
private int now = 0;
Scanner sc = new Scanner(System.in);
/*
* 構(gòu)造函數(shù)
*/
Tree_Link(){
}
/*
* 鏈表建立
*/
public Tree Link_Build(Tree head){
// Tree head = new Tree();//頭節(jié)點(diǎn)
System.out.println("繼續(xù)code：1");
int flag = sc.nextInt();
if(flag != 1){
return head;
}else{
System.out.println("\n\n\n輸入 節(jié)點(diǎn)信息：");
head.SetCode(sc.nextInt());
System.out.println("\n建立 左 子樹(shù)code：1 否則：0");
flag = sc.nextInt();
if(flag == 1){
now++;
Tree LTree = new Tree();
head.SetLtree(LTree);
LTree.SetFronttree(head);//設(shè)置父母節(jié)點(diǎn)
Link_Build( head.GetLtree() );
}
System.out.println("\n當(dāng)前位置：" + head.GetCode());
System.out.println("\n建立 右 子樹(shù)code：1 否則：0");
flag = sc.nextInt();
if(flag == 1){
now++;
Tree Rtree = new Tree();
head.SetRtree(Rtree);
Rtree.SetFronttree(head);//設(shè)置父母節(jié)點(diǎn)
Link_Build( head.GetRtree() );
}
if( now > save ){
save = now;
}
now--;
}
return head;
}
/*
* 輸出樹(shù)
*/
public Tree output(Tree head){
int flag;
if(head.GetCode() == -1){
return head;
}else{
System.out.println("\n當(dāng)前位置：" + head.GetCode());
System.out.println(head.GetLtree() != null);
if(head.GetLtree() != null){
System.out.println("\n訪(fǎng)問(wèn) 左子樹(shù):");
output( head.GetLtree() );
}
if(head.GetRtree() != null){
System.out.println("\n訪(fǎng)問(wèn) 右子樹(shù):");
output( head.GetRtree() );
}
}
return head;
}
/*
* 獲得高度
*/
public int GetSave(){
return this.save;
}
/*
* 非遞歸 前序遍歷
*/
public void Front_Traverse(Tree head){
Tree star = head;//退出標(biāo)記
int choose = 1; //左
int flag = 1; //右
System.out.println( "<---前序遍歷--->" + head.GetCode() );//先訪(fǎng)問(wèn)根
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;//退出標(biāo)記
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){//因?yàn)樽筮厼榭斩祷?
System.out.println( "<-1--中序遍歷--->" + head.GetCode());
}
head = head.GetRtree();
choose = 1;
}else if( flag == 0 && choose == 0 && head == star){
break;
}else{
int area = 0;//判斷哪邊回來(lái)
flag = 1;
choose = 1;
if(head == head.GetFronttree().GetRtree()){
area = 1;//右邊回來(lái)
flag = 0;
choose = 0;
}
if(head == head.GetFronttree().GetLtree()){
area = 2;//左邊回來(lái)
choose = 0;
flag = 1;
}
if( head.GetLtree() == null && head.GetRtree() == null ){//因?yàn)樽筮厼榭斩祷?
System.out.println( "<-2--中序遍歷--->" + head.GetCode());
}
head = head.GetFronttree();
if( area == 2){//因?yàn)樽筮呍L(fǎng)問(wèn)完返回
System.out.println( "<-3--中序遍歷--->" + head.GetCode());
}
System.out.println("獲得 父母" + head.GetCode());
System.out.println( "\n\n\n" );
}
}
}
/*
* 非遞歸 后續(xù)遍歷
*/
public void Bottom_Traverse(Tree head){
Tree star = head;//退出標(biāo)記
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;//判斷哪邊回來(lái)
flag = 1;
choose = 1;
if(head == head.GetFronttree().GetRtree()){
area = 1;//右邊回來(lái)
flag = 0;
choose = 0;
}
if(head == head.GetFronttree().GetLtree()){
choose = 0;
flag = 1;
}
if(head.GetRtree() == null){//因?yàn)橛疫厼榭斩祷?
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 類(lèi)實(shí)現(xiàn)：
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;
}
/*
* 樹(shù)內(nèi)容查看方法：
*/
public void SetCode(int code){//設(shè)置編號(hào)
this.code = code;
}
public int GetCode(){ //獲取編號(hào)
return this.code;
}
/*
* 設(shè)置父母指針：
*/
public void SetFronttree(Tree Front){
this.Fonttree = Front;
}
public Tree GetFronttree(){
System.out.println("獲得 父母");
return this.Fonttree;
}
/*
* 設(shè)置左子女：
*/
public void SetLtree(Tree Ltree){
this.Ltree = Ltree;
}
public Tree GetLtree(){
System.out.println("獲得左子樹(shù)");
return this.Ltree;
}
/*
* 設(shè)置右子女：
*/
public void SetRtree(Tree Rtree){
this.Rtree = Rtree;
}
public Tree GetRtree(){
System.out.println("獲得右子樹(shù)");
return this.Rtree;
}
}
3. 主函數(shù)測(cè)試：
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二叉樹(shù)高度-->" + link_1st.GetSave());
link_1st.output(head);
System.out.println("Output Over !");
System.out.println("\n\n<----------------前------------------>\n前序訪(fǎng)問(wèn)根：");
link_1st.Front_Traverse(head);
System.out.println("\n\n<----------------中------------------>\n中序訪(fǎng)問(wèn)根：");
link_1st.Center_Traverse(head);
System.out.println("\n\n<----------------后------------------>\n后序訪(fǎng)問(wèn)根：");
link_1st.Bottom_Traverse(head);
System.out.println("\n\n\n\nText over !\n\n\n");
}
}
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
相關(guān)文章
mybatis中<if>標(biāo)簽bool值類(lèi)型為false判斷方法
這篇文章主要給大家介紹了關(guān)于mybatis中<if>標(biāo)簽bool值類(lèi)型為false判斷方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用mybatis具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
tomcat目錄結(jié)構(gòu)簡(jiǎn)介_(kāi)動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
這篇文章主要介紹了tomcat目錄結(jié)構(gòu)簡(jiǎn)介_(kāi)動(dòng)力節(jié)點(diǎn)Java學(xué)院整理的相關(guān)資料,需要的朋友可以參考下2017-07-07
reactor-logback的AsyncAppender執(zhí)行流程源碼解讀
這篇文章主要為大家介紹了reactor-logback的AsyncAppender執(zhí)行流程源碼解讀,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12
Spring Boot中使用activiti的方法教程（一）
最近一直研究springboot，下面這篇文章主要給大家介紹了關(guān)于Spring Boot中使用activiti的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，需要的朋友可以參考借鑒，下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2018-08-08
java實(shí)現(xiàn)文件導(dǎo)入導(dǎo)出
這篇文章主要介紹了java實(shí)現(xiàn)文件導(dǎo)入導(dǎo)出的方法和具體示例代碼，非常的簡(jiǎn)單實(shí)用，有需要的小伙伴可以參考下2016-04-04
MyBatis中使用foreach循環(huán)的坑及解決
這篇文章主要介紹了MyBatis中使用foreach循環(huán)的坑及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-01-01
RESTful是一種web軟件風(fēng)格，它不是標(biāo)準(zhǔn)也不是協(xié)議，它不一定要采用,只是一種風(fēng)格，它倡導(dǎo)的是一個(gè)資源定位(url)及資源操作的風(fēng)格，這篇文章主要介紹了SpringBoot使用RESTful接口2022-11-11
Redis工具類(lèi)封裝RedisUtils的使用示例
本文主要介紹了Redis工具類(lèi)封裝RedisUtils的使用示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了Spring緩存機(jī)制實(shí)例代碼，分享了相關(guān)代碼示例，小編覺(jué)得還是挺不錯(cuò)的，具有一定借鑒價(jià)值，需要的朋友可以參考下2018-02-02
這篇文章主要介紹了java批量下載生成zip壓縮包的思路詳解,設(shè)計(jì)思路大概是本地先創(chuàng)建一個(gè)zip文件,將批量下載的文件依次放入zip文件中,將zip文件返回給前端,本文結(jié)合實(shí)例代碼講解的非常詳細(xì),需要的朋友可以參考下2024-01-01