1 關(guān)于二叉樹的生成--遍歷--反轉(zhuǎn)-等操作的JAVA版實(shí)現(xiàn)

? ? ? 二叉樹:是一種有兩個(gè)子節(jié)點(diǎn)的樹形結(jié)構(gòu),分為根節(jié)點(diǎn),左子數(shù),右子數(shù)

平衡二叉樹:平衡二叉樹基本定義是指樹中任一結(jié)點(diǎn)的左、右子樹高度大致相同。平衡二叉樹有很多種最著名的是由前蘇聯(lián)數(shù)學(xué)家Adels提出的，我們也稱其為稱為AVL樹。平衡二叉樹(AVL樹)定義如下：平衡二叉樹或者是一棵空樹，或者是具有以下性質(zhì)的二叉排序樹：(1)它的左子樹和右子樹的高度之差絕對值不超過1；(2)它的左子樹和右子樹都是平衡二叉樹。(如圖所示)

2 JAVA定義一個(gè)二叉樹鏈表

? ? ? ? ? 定義結(jié)構(gòu)類:public class TreeNode {

? ? ? ? ? ? ? ? ? ? ? ? int data;//根節(jié)點(diǎn)數(shù)據(jù)

? ? ? ? ? ? ? ? ? ? ? TreeNode left;

? ? ? ? ? ? ? ? ? ? TreeNode right;//左右節(jié)點(diǎn)

? ? ? ? public TreeNode(int data){//將左右節(jié)點(diǎn)重置為根節(jié)點(diǎn),其左右節(jié)點(diǎn)為空

? ? ? ? ? ? ? ? ? ? ? ? ? this.data=data;

? ? ? ? ? ? ? ? ? ? ? ? ? left=null;

? ? ? ? ? ? ? ? ? ? right=null;}

? ? 現(xiàn)在我們已經(jīng)定義完了二叉樹的結(jié)構(gòu)和構(gòu)造方法.包括新的二叉樹生成方法.現(xiàn)在能夠讓一組數(shù)自動生成一個(gè)二叉樹了.

3 定義二叉樹的先序--中序---后序遍歷方法

先序:先訪問根結(jié)點(diǎn)，再訪問左子樹，然后再訪問右子樹

中序:先訪問左子樹，再訪問，然后再訪問右子樹

后序:先訪問左子樹，再訪問右子樹，然后再訪問根結(jié)點(diǎn)

這里我們用遞歸方法實(shí)現(xiàn),原理很簡單,就不贅述了.

4 生成鏡像二叉樹,也就是實(shí)現(xiàn)二叉樹的反轉(zhuǎn).左子樹變?yōu)橛易訕?右子數(shù)變?yōu)樽笞訕?

? (原理如圖,圖片來自互聯(lián)網(wǎng))

使用遞歸法進(jìn)行反轉(zhuǎn)10多行就解決了,使用遍歷法也不難.其實(shí)兩種算法的實(shí)現(xiàn)核心都是一樣的,都是輪詢進(jìn)行左右子樹交換,只是實(shí)現(xiàn)的路徑不同.代碼看圖.

5 主函數(shù)進(jìn)行二叉樹生成---遍歷---反轉(zhuǎn)---再遍歷的操作

代碼

運(yùn)行結(jié)果

6二叉樹變成平衡二叉樹,(鏈表反轉(zhuǎn),雙向鏈表反轉(zhuǎn)等),源碼在github上

地址:https://github.com/yanshilong1/Mylgorithm

謝謝閱讀.