本篇內(nèi)容主要講解“Java實現(xiàn)二叉樹的遍歷方法是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“Java實現(xiàn)二叉樹的遍歷方法是什么”吧!
十載的商河網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。成都營銷網(wǎng)站建設(shè)的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整商河建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“商河網(wǎng)站設(shè)計”,“商河網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。
遍歷或稱周游，traversal。系統(tǒng)地訪問數(shù)據(jù)結(jié)構(gòu)中的節(jié)點，每個節(jié)點都正好被訪問到一次。
三種深度優(yōu)先遍歷的遞歸定義：
前序法（tLR次序，preorder traversal）：訪問根結(jié)點，按前序遍歷左子樹；按前序遍歷右子樹。
中序法（LtR次序，inorder traversal）：按中序遍歷左子樹；訪問根結(jié)點；按中序遍歷右子樹。
后序法（LRt次序，postorder traversal）：按后序遍歷左子樹；按后序遍歷右子樹；訪問根結(jié)點。
public static ListpreOrderTraverseByRecursion(BinaryTreeNode root, List list) { if (root != null) { list.add(root.getKey());//前序法訪問節(jié)點 preOrderTraverseByRecursion(root.getLeft(), list); //list.add(root.getKey());//中序法訪問節(jié)點 preOrderTraverseByRecursion(root.getRight(), list); //list.add(root.getKey());//后序法訪問節(jié)點 } return list; }
遞歸算法非常簡潔，推薦使用，當(dāng)前的編譯系統(tǒng)優(yōu)化效率很不錯了。特殊情況用棧模擬遞歸，深度優(yōu)先遍歷的回溯特點和棧的工作原理一致，有些應(yīng)用環(huán)境資源限制不適合遞歸。
實現(xiàn)
/** * 先序遍歷（非遞歸） * 通過棧來避免遞歸（有節(jié)點入棧） * * @param root */ public static ListpreOrderTraverseByNonRecursion(BinaryTreeNode root) { List list = new ArrayList<>();// 用于存放遍歷后的結(jié)果 Stack stack = new Stack();// 用于存放右子樹節(jié)點 BinaryTreeNode p = root; //左子樹和右子樹都未遍歷時，遍歷 while (p != null || stack.size() > 0) { if (p != null) { //左子樹不為空時，遍歷左子樹 list.add(p.getKey());//當(dāng)前節(jié)點輸出 stack.push(p.getRight());//右子樹入棧，待左子樹遍歷完后遍歷右子樹 p = p.getLeft();//遍歷左子樹 } else { //左子樹遍歷完后，遍歷右子樹 p = stack.pop(); } } return list; }
實現(xiàn)
/** * 中序遍歷（非遞歸） * * @param root */ public static ListinOrderTraverseByNonRecursion(BinaryTreeNode root) { List list = new ArrayList<>(); Stack stack = new Stack<>(); BinaryTreeNode current = root; //遍歷節(jié)點的左子樹并將根結(jié)點入棧，直到左子樹為null時，然后出棧獲取節(jié)點并遍歷該節(jié)點的右子樹的左子樹直到為null while(current != null || !stack.empty()){ if(current != null){ stack.push(current); current = current.getLeft(); }else{ BinaryTreeNode top = stack.pop(); list.add(top.getKey()); current = top.getRight(); } } return list; }
實現(xiàn)
/** * 后續(xù)遍歷（非遞歸） * * @param root */ public static ListpostOrderTraverseByNonRecursion(BinaryTreeNode root) { Stack stack = new Stack<>(); List list = new ArrayList<>(); stack.push(root); BinaryTreeNode current; while (stack.isEmpty() == false) { current = stack.pop(); if (current != null) { list.add(current.getKey()); stack.push(current.getLeft()); stack.push(current.getRight()); } } Collections.reverse(list); return list; }
從二叉樹的第0層（根結(jié)點）開始，自上而下，追層遍歷；在同一層中，按照從左到右的順序?qū)?jié)點逐一訪問。 特點是先遍歷先訪問，符合隊列的特征，通過隊列來實現(xiàn)。 實現(xiàn)如下：
/** * 層序遍歷（寬度優(yōu)先遍歷） * 特點是先進先出，符合隊列的特性 * * @param root * @return */ public static ListlayerOrderTraverse(BinaryTreeNode root) { List list = new ArrayList<>(); LinkedList queue = new LinkedList<>(); BinaryTreeNode current; queue.offer(root); while (!queue.isEmpty()){ current = queue.poll(); list.add(current.getKey()); if(current.getLeft() != null){ queue.addLast(current.getLeft()); } if(current.getRight() != null){ queue.addLast(current.getRight()); } } return list; }
先來個結(jié)論及說明：
僅一個先（中、后）序序列不能構(gòu)造唯一一顆二叉樹（原因：無法確定左右子樹或根結(jié)點）
僅先（后）序序列和中序序列可以構(gòu)造唯一一顆二叉樹（原因：先序序列和后序序列無法構(gòu)造唯一一顆二叉樹）
用擴充先（后）序序列可以構(gòu)造唯一一顆二叉樹
用擴充中序序列不能構(gòu)造唯一一顆二叉樹
實現(xiàn)：
/** * 根據(jù)先序序列和中序序列構(gòu)造二叉樹（遞歸實現(xiàn)） ** 先序序列第一個元素是樹的根結(jié)點，從中序序列中找出與根結(jié)點所在位置k: * 1.確定根結(jié)點的左子樹和右子樹的中序序列：該位置之前的元素就是根結(jié)點左子樹的中序序列，該位置之后的元素就是根結(jié)點的右子樹的中序序列 * 2.確定根結(jié)點的左子樹和右子樹的先序序列：先序序列第一個元素往后k元素就是根結(jié)點左子樹的先序序列，k+1位置之后就是根結(jié)點右子樹的先序序列 *
*
* perOrder[i]~perOrder[j] 是子樹的先序序列 * inOrder[s]~inOrder[t] 是子樹的中序序列 * * @param perOrder * @param inOrder * @param i * @param j * @param s * @param t * @return */ public static BinaryTreeNode buildTreeByPerOrderAndInOrder(Integer[] perOrder, Integer[] inOrder, int i, int j, int s, int t) { if (i > j) { return null; } BinaryTreeNode root = new BinaryTreeNode(perOrder[i]); int k; k = s; while (k <= t && inOrder[k] != perOrder[i]) { k++; } if (k > t) { return null; } root.setLeft(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + 1, j + k - s, s, k - 1)); root.setRight(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + k - s + 1, j, k + 1, t)); return root; }
一個節(jié)點的左子樹和右子樹存在三種組合方式，左子樹為null，右子樹為null，左右子樹都不為null。 運用遞歸思想時，按這三種情況分析左右子樹的后序序列和中序序列。實現(xiàn)如下：
重慶分公司
重慶分公司
/**
* 根據(jù)后序序列和中序序列構(gòu)造二叉樹（遞歸實現(xiàn)）
*
* postOrder[i]~postOrder[j]是子樹的后序序列
* inOrder[s]~inOrder[t]是子樹的中序序列
*
* @param postOrder
* @param inOrder
* @param i
* @param j
* @param s
* @param t
* @return
*/
public static BinaryTreeNode buildTreeByPostOrderAndInOrder(Integer[] postOrder, Integer[] inOrder, int i, int j, int s, int t) {
if (i > j) {
return null;
}
BinaryTreeNode root = new BinaryTreeNode(postOrder[j]);
int k;
k = s;
while (k <= t && inOrder[k] != postOrder[j]) {
k++;
}
if (k > t) {
return null;
}
//左子樹個數(shù)
int countLeft = k - s;
//右子樹個數(shù)
int countRight = t - k;
if (countLeft == 0) {
//左子樹為null
root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countRight, j - 1, t - countRight + 1, t));
} else if (countRight == 0) {
//右子樹為null
root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countLeft, j - 1, t - countLeft, t - countRight - 1));
} else {
//左、右子樹不為null
root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, i, i + countLeft - 1, s, s + countLeft - 1));
root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - 1 - countRight + 1, j - 1, t - countRight + 1, t));
}
return root;
}到此，相信大家對“Java實現(xiàn)二叉樹的遍歷方法是什么”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
