Java中二叉樹的先序、中序、后序遍歷以及代碼實現(xiàn)
更新時間：2023年11月04日 08:31:35 作者：夢想不會滅
這篇文章主要介紹了Java中二叉樹的先序、中序、后序遍歷以及代碼實現(xiàn),一棵二叉樹是結點的一個有限集合,該集合或者為空,或者是由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成,需要的朋友可以參考下
一、二叉樹的三種遍歷方式
二叉樹的遍歷主要有三種：先(根)序遍歷（根左右），中(根)序遍歷（左根右），后(根)序遍歷（左右根），以下圖為例分別說明。
1、先(根)序遍歷（根左右）
先序遍歷的原則是：先根、再左、再右。 即：ABCDEFGH
2、中(根)序遍歷（左根右）
中序遍歷的原則是：先左、再根、再右。 即：BDCEAFHG
3、后(根)序遍歷（左右根）
后序遍歷的原則是：先左、再右、再根。 即：DECBHGFA
二、代碼實現(xiàn)二叉樹的三種遍歷方式
/**
* 下文中用到的TreeNode類
*/
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
1、遞歸方式實現(xiàn)
/**
* 先序遍歷的原則是：先根、再左、再右。
* @param root
* @param list
*/
private void preorder(TreeNode root, List<Integer> list){
if(root != null){
list.add(root.val);
preorder(root.left,list);
preorder(root.right,list);
}
}
/**
* 中序遍歷的原則是：先左、再根、再右
* @param root
* @param list
*/
private void inorder(TreeNode root, List<Integer> list){
if(root != null){
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
}
/**
* 后序遍歷的原則是：先左、再右、再根
* @param root
* @param list
*/
private void postorder(TreeNode root, List<Integer> list){
if(root != null){
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
}
2、迭代方式實現(xiàn)
/**
* 先序遍歷的原則是：先根、再左、再右。
* 1.輔助變量 tempNode 初始化為根節(jié)點
* 2.當 tempNode != null 時，就保存這個節(jié)點值到 list 中，然后將其入棧并置 tempNode為它自己的左子節(jié)點
* 3.當 tempNode == null 時，說明已經(jīng)遍歷到二叉樹的左下節(jié)點了，這時前序遍歷應該遍歷右子樹了，首先 pop 出已經(jīng)遍歷保存過的父節(jié)點，然后置 tempNode 為 pop 出的父節(jié)點的右子節(jié)點
* @param root
* @param list
*/
private void preorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while(!stack.isEmpty() || tempNode != null){
if (tempNode != null) {
list.add(tempNode.val);
stack.push(tempNode);
tempNode = tempNode.left;
} else {
tempNode = stack.pop();
tempNode = tempNode.right;
}
}
}
/**
* 中序遍歷的原則是：先左、再根、再右
* 1.輔助變量 tempNode 初始化 root
* 3.當棧非空或 tempNode 非 null 時，循環(huán)
* 3.1 tempNode != null 時，說明還有左子節(jié)點存在，將 tempNode 入棧，并且將 tempNode 置為它自己的左子節(jié)點
* （和前序遍歷的區(qū)別在于這里遍歷到先不保存到 list 中，出棧的時候再將其保存到 list 中）
* 3.2 tempNode == null 時，說明到二叉樹左下的節(jié)點了，這時棧頂?shù)母腹?jié)點出棧賦值給 tempNode ，并保存節(jié)點值到 list ，將 tempNode 置為棧頂節(jié)點的右子節(jié)點繼續(xù)循環(huán)
* @param root
* @param list
*/
private void inorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while(!stack.isEmpty() || tempNode != null){
if (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.left;
} else {
tempNode = stack.pop();
list.add(tempNode.val);
tempNode = tempNode.right;
}
}
}
/**
* 后序遍歷的原則是：先左、再右、再根
* 1.對應前序遍歷的反操作：
* 2.前序遍歷從尾部添加元素，后序遍歷從頭部添加元素
* 3.前序遍歷去左子樹，后序遍歷去右子樹
* @param root
* @param list
*/
private void postorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while (!stack.isEmpty() || tempNode != null) {
if (tempNode != null) {
stack.push(tempNode);
list.add(0, tempNode.val);
tempNode = tempNode.right;
} else {
tempNode = stack.pop();
tempNode = tempNode.left;
}
}
}
到此這篇關于Java中二叉樹的先序、中序、后序遍歷以及代碼實現(xiàn)的文章就介紹到這了,更多相關Java二叉樹的先序、中序、后序遍歷內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了拳皇Java簡單小程序，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03
WeakHashMap?和?HashMap?區(qū)別及使用場景
這篇文章主要為大家介紹了WeakHashMap?和?HashMap?的區(qū)別是什么以及何時使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-11-11
這篇文章主要為大家介紹了java自旋鎖和JVM對鎖的優(yōu)化示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09
在日常開發(fā)和運維工作中,管理基于Java的應用程序是一項基礎且頻繁的任務,本文將通過一個示例腳本,展示如何利用Shell腳本簡化這一流程,實現(xiàn)Java應用的一鍵式啟動、停止與重啟操作,本腳本不僅提升了工作效率,還確保了操作的標準化與可靠性2024-06-06
Fluent Mybatis,原生Mybatis,Mybatis Plus三者功能對比
本文主要介紹了Fluent Mybatis,原生Mybatis,Mybatis Plus三者功能對比，分享給大家，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要為大家詳細介紹了SpringBoot如何使用Redis和Redis緩存，文中的示例代碼講解詳細，對我們學習SpringBoot有一定的幫助，需要的可以參考一下2022-06-06
Java如何通過反射機制獲取數(shù)據(jù)類對象的屬性及方法
文章介紹了如何使用Java反射機制獲取類對象的所有屬性及其對應的get、set方法,以及如何通過反射機制實現(xiàn)類對象的實例化,感興趣的朋友跟隨小編一起看看吧2025-01-01
這篇文章主要介紹了Springboot文件上傳功能簡單測試,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05
本文是一個Struts2的簡單入門教程，比較簡單，希望能給大家做一個參考。2016-06-06
這篇文章主要介紹了使用Java的Graphics類進行繪圖的方法,是Java的GUI編程的基礎,需要的朋友可以參考下2015-10-10