Java中二叉樹的建立和各種遍歷實例代碼
這是個常見的面試題,比如說通過二叉樹的先序和中序遍歷,得到二叉樹的層序遍歷等問題
先序+中序->建樹
假設(shè)現(xiàn)在有個二叉樹,如下:
此時遍歷順序是:
PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG
現(xiàn)在給出先序(preOrder)和中序(InOrder),建立一顆二叉樹
或者給出中序(InOrder)和后序(PostOrder), 建立二叉樹,其實是一樣的
樹節(jié)點的定義:
class Tree{ char val; Tree left; Tree right; Tree(char val, Tree left, Tree right){ this.val = val; this.left = left; this.right = right; } Tree(){ } Tree(char val){ this.val = val; this.left = null; this.right =null; } }
建樹:
public static Tree buildTree(char[] preOrder, char[] inOrder){ //preOrder是先序序列 //inOrder是中序序列 if(preOrder == null || preOrder.length == 0){ return null; } Tree root = new Tree(preOrder[0]); //找到inOrder中的root的位置 int inOrderIndex = 0; for (char i = 0; i < inOrder.length; i++){ if(inOrder[i] == root.val){ inOrderIndex = i; } } //preOrder的左子樹和右子樹部分 char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex); char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+inOrderIndex, preOrder.length); //inOrder的左子樹和右子樹部分 char[] inOrderLeft = Arrays.copyOfRange(inOrder, 0, inOrderIndex); char[] inOrderRight = Arrays.copyOfRange(inOrder, inOrderIndex+1, inOrder.length); //遞歸建立左子樹和右子樹 Tree leftChild = buildTree(preOrderLeft, inOrderLeft); Tree rightChild = buildTree(preOrderRight, inOrderRight); root.left = leftChild; root.right = rightChild; return root; }
中序+后序去建樹其實是一樣的,此處不寫了
各種遍歷
后序遍歷
public static void postOrderPrint(Tree root){ //后續(xù)遍歷 //左右根 if(root.left != null){ postOrderPrint(root.left); } if(root.right != null){ postOrderPrint(root.right); } System.out.print(root.val + " "); }
舉一反三,先序和中序是一樣的,此處不寫了
層序遍歷
可以用一個隊列Queue,初始先把root節(jié)點加入到隊列,當(dāng)隊列不為空的時候取隊列頭的節(jié)點node,打印node的節(jié)點值,如果node的左右孩子不為空將左右孩子加入到隊列中即可
public static void layerOrderPrint(Tree root){ if(root == null){ return; } //層序遍歷 Queue<Tree> qe = new LinkedList<Tree>(); qe.add(root); while(!qe.isEmpty()){ Tree node = qe.poll(); System.out.print(node.val + " "); if(node.left != null){ qe.add(node.left); } if(node.right != null){ qe.add(node.right); } } }
深度優(yōu)先和廣度優(yōu)先
其實就是換個說法而已,深度優(yōu)先不就是先序遍歷嘛,廣度優(yōu)先就是層序遍歷
public static void deepFirstPrint(Tree root){ //深度優(yōu)先遍歷等價于先序遍歷 //所以可以直接使用先序遍歷 if(root == null){ return; } System.out.print(root.val + " "); if(root.left != null){ deepFirstPrint(root.left); } if(root.right != null){ deepFirstPrint(root.right); } } public static void deepFirstPrintNoneRec(Tree root){ //深度優(yōu)先遍歷的非遞歸形式 if(root == null){ return; } Stack<Tree> st = new Stack<Tree>(); st.add(root); while(!st.isEmpty()){ Tree node = st.pop(); System.out.print(node.val + " "); //棧是后進(jìn)先出的 //先加右孩子后加左孩子 if(node.right != null){ st.add(node.right); } if(node.left != null){ st.add(node.left); } } }
main函數(shù):
public static void main(String[] args) { char[] preOrder = "GDAFEMHZ".toCharArray(); char[] inOrder = "ADEFGHMZ".toCharArray(); Tree root = Main.buildTree(preOrder, inOrder); // Main.postOrderPrint(root); //后序遍歷 // Main.layerOrderPrint(root); //層序遍歷 // Main.deepFirstPrint(root); //深度優(yōu)先遍歷 // Main.deepFirstPrintNoneRec(root); //深度優(yōu)先遍歷的非遞歸版本 }
總結(jié)
以上就是本文關(guān)于Java中二叉樹的建立和各種遍歷實例代碼的全部內(nèi)容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:
如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!
- java棧實現(xiàn)二叉樹的非遞歸遍歷的示例代碼
- Java二叉樹的四種遍歷(遞歸和非遞歸)
- JAVA二叉樹的幾種遍歷(遞歸,非遞歸)實現(xiàn)
- java二叉樹的幾種遍歷遞歸與非遞歸實現(xiàn)代碼
- java二叉樹的非遞歸遍歷
- java 對稱二叉樹的判斷
- Java 最優(yōu)二叉樹的哈夫曼算法的簡單實現(xiàn)
- Java實現(xiàn)二叉樹的建立、計算高度與遞歸輸出操作示例
- java編程題之從上往下打印出二叉樹
- java實現(xiàn)按層遍歷二叉樹
- java實現(xiàn)二叉樹遍歷的三種方式
- Java二叉樹的遍歷思想及核心代碼實現(xiàn)
- Java實現(xiàn)二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法示例
- Java實現(xiàn)打印二叉樹所有路徑的方法
- Java實現(xiàn)的二叉樹常用操作【前序建樹,前中后遞歸非遞歸遍歷及層序遍歷】
- java編程求二叉樹最大路徑問題代碼分析
- Java二叉樹路徑和代碼示例
- Java源碼解析之平衡二叉樹
相關(guān)文章
SpringBoot集成Shiro進(jìn)行權(quán)限控制和管理的示例
這篇文章主要介紹了SpringBoot集成Shiro進(jìn)行權(quán)限控制和管理的示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2018-03-03使用SpringBoot+OkHttp+fastjson實現(xiàn)Github的OAuth第三方登錄
這篇文章主要介紹了使用SpringBoot+OkHttp+fastjson實現(xiàn)Github的OAuth第三方登錄,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02SpringCloud網(wǎng)關(guān)(Zuul)如何給多個微服務(wù)之間傳遞共享參數(shù)
這篇文章主要介紹了SpringCloud網(wǎng)關(guān)(Zuul)如何給多個微服務(wù)之間傳遞共享參數(shù),具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-03-03java并發(fā)數(shù)據(jù)包Exchanger線程間的數(shù)據(jù)交換器
這篇文章主要為大家介紹了java并發(fā)數(shù)據(jù)包使用數(shù)據(jù)交換器Exchanger來進(jìn)行線程之間的數(shù)據(jù)交換。有需要的朋友可以借鑒參考下,希望能夠有所幫助2022-03-03啟用Spring事務(wù)管理@EnableTransactionManagement示例解析
這篇文章主要為大家介紹了啟用Spring事務(wù)管理@EnableTransactionManagement示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09