Java二叉樹的遍歷思想及核心代碼實現(xiàn)
二叉樹在計算機中的存儲方式往往線性結(jié)構(gòu),線性存儲分為順序存儲和鏈式存儲,將二叉樹按層序編號。
順序結(jié)構(gòu):按編號的順序進行存儲,對于完全二叉樹而言,順序存儲可以反映二叉樹的邏輯,但是對于大多數(shù)的二叉樹則無法反映其邏輯關(guān)系,不過可以用 ^ 來代替不存在的結(jié)點,但是如果這個樹是一個右斜樹,就非常浪費存儲空間。所以二叉樹的存儲形式一般為鏈式存儲結(jié)構(gòu)。
鏈式存儲:每一個結(jié)點都分有一個數(shù)據(jù)域(data)和兩個指針域(lchild和rchild),指針域分別指向左孩子和右孩子,若為空則為null。遍歷方式有四種:前序遍歷、中序遍歷、后序遍歷及層序遍歷,前三種遍歷方式采用遞歸的思想進行遍歷。
為方便理解,畫一個樹并結(jié)合代碼
前序遍歷:若二叉樹為空則返回null,否則先訪問根節(jié)點然后遍歷左子樹,再遍歷右子樹,如圖:ABDGHCEIF
代碼如下:
void PreOrderTraverse(BiTree T) { if(T == NULL) /*為空返回*/ return; printf("%c",T->data); /*輸出該結(jié)點的信息*/ PreOrderTraverse(T->lchild); /*遍歷左子樹*/ PreOrderTraverse(T->rchild); /*遍歷右子樹*/ }
中序遍歷:若二叉樹為空則返回null,否則從根節(jié)點出發(fā)訪問左子樹,然后訪問根結(jié)點,最后訪問右子樹,如圖:GDHBAEICF
代碼如下:
void InOrderTraverse(BiTree T) { if(T == NULL) /*為空返回*/ return; InOrderTraverse(T->lchild); /*遍歷左子樹*/ printf("%c",T->data); /*輸出該結(jié)點的信息*/ InOrderTraverse(T->rchild); /*遍歷右子樹*/ }
后序遍歷:若二叉樹為空則返回null,否則以先葉子后結(jié)點的方式進行訪問最后到根結(jié)點遍歷結(jié)束,如圖:GHDBIEFCA
代碼如下:
void PostOrderTraverse(BiTree T) { if(T == NULL) /*為空返回*/ return; PostOrderTraverse(T->lchild); /*遍歷左子樹*/ PostOrderTraverse(T->rchild); /*遍歷右子樹*/ printf("%c",T->data); /*輸出該結(jié)點的信息*/ }
層序遍歷:若二叉樹為空則返回null,否則從第一層開始進行訪問,如圖:ABCDEFGHI,按編號進行輸出或操作即可
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接
相關(guān)文章
MyBatis-Plus介紹及Spring Boot 3集成指南
本文介紹了MyBatis-Plus的基本特性及其與Spring Boot 3的集成步驟,通過使用MyBatis-Plus,開發(fā)者可以快速地搭建和開發(fā)數(shù)據(jù)訪問層,同時提高代碼質(zhì)量和開發(fā)效率,感興趣的朋友一起看看吧2024-05-05SpringBoot集成screw實現(xiàn)數(shù)據(jù)庫文檔生成的代碼示例
數(shù)據(jù)庫設(shè)計文檔是項目技術(shù)文檔的重要組成部分,Screw 是一款開源的數(shù)據(jù)庫文檔生成工具,它支持多種數(shù)據(jù)庫類型,并能生成豐富格式的文檔,本文將通過一個實際的例子,展示如何使用 Spring Boot 集成 Screw 生成數(shù)據(jù)庫設(shè)計文檔2024-07-07詳解Spring注解--@Autowired、@Resource和@Service
本篇文章主要介紹最重要的三個Spring注解,也就是@Autowired、@Resource和@Service,具有很好的參考價值。下面跟著小編一起來看下吧2017-05-05Spring中ContextLoaderListener監(jiān)聽詳解
這篇文章主要介紹了Spring中ContextLoaderListener監(jiān)聽詳解,SpringMVC啟動時會啟動WebApplicationContext類型的容器,并且會調(diào)用之前分析的refresh方法,需要的朋友可以參考下2024-01-01SpringBoot中的定時任務(wù)和異步調(diào)用詳解
這篇文章主要介紹了SpringBoot中的定時任務(wù)和異步調(diào)用詳解,SpringBoot 定時任務(wù)是一種在SpringBoot應(yīng)用中自動執(zhí)行任務(wù)的機制,通過使用Spring框架提供的@Scheduled注解,我們可以輕松地創(chuàng)建定時任務(wù),需要的朋友可以參考下2023-10-10