溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“Java實現二叉樹的遍歷方法是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java實現二叉樹的遍歷方法是什么”吧!
遍歷或稱周游，traversal。系統地訪問數據結構中的節點，每個節點都正好被訪問到一次。
三種深度優先遍歷的遞歸定義：
前序法（tLR次序，preorder traversal）：訪問根結點，按前序遍歷左子樹；按前序遍歷右子樹。
中序法（LtR次序，inorder traversal）：按中序遍歷左子樹；訪問根結點；按中序遍歷右子樹。
后序法（LRt次序，postorder traversal）：按后序遍歷左子樹；按后序遍歷右子樹；訪問根結點。
public static List<Integer> preOrderTraverseByRecursion(BinaryTreeNode root, List<Integer> list) {
if (root != null) {
list.add(root.getKey());//前序法訪問節點
preOrderTraverseByRecursion(root.getLeft(), list);
//list.add(root.getKey());//中序法訪問節點
preOrderTraverseByRecursion(root.getRight(), list);
//list.add(root.getKey());//后序法訪問節點
}
return list;
}遞歸算法非常簡潔，推薦使用，當前的編譯系統優化效率很不錯了。特殊情況用棧模擬遞歸，深度優先遍歷的回溯特點和棧的工作原理一致，有些應用環境資源限制不適合遞歸。
實現
/**
* 先序遍歷（非遞歸）
* 通過棧來避免遞歸（有節點入棧）
*
* @param root
*/
public static List<Integer> preOrderTraverseByNonRecursion(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();// 用于存放遍歷后的結果
Stack<BinaryTreeNode> stack = new Stack();// 用于存放右子樹節點
BinaryTreeNode p = root;
//左子樹和右子樹都未遍歷時，遍歷
while (p != null || stack.size() > 0) {
if (p != null) { //左子樹不為空時，遍歷左子樹
list.add(p.getKey());//當前節點輸出
stack.push(p.getRight());//右子樹入棧，待左子樹遍歷完后遍歷右子樹
p = p.getLeft();//遍歷左子樹
} else { //左子樹遍歷完后，遍歷右子樹
p = stack.pop();
}
}
return list;
}實現
/**
* 中序遍歷（非遞歸）
*
* @param root
*/
public static List<Integer> inOrderTraverseByNonRecursion(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<BinaryTreeNode> stack = new Stack<>();
BinaryTreeNode current = root;
//遍歷節點的左子樹并將根結點入棧，直到左子樹為null時，然后出棧獲取節點并遍歷該節點的右子樹的左子樹直到為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;
}實現
/**
* 后續遍歷（非遞歸）
*
* @param root
*/
public static List<Integer> postOrderTraverseByNonRecursion(BinaryTreeNode root) {
Stack<BinaryTreeNode> stack = new Stack<>();
List<Integer> 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層（根結點）開始，自上而下，追層遍歷；在同一層中，按照從左到右的順序對節點逐一訪問。 特點是先遍歷先訪問，符合隊列的特征，通過隊列來實現。 實現如下：
/**
* 層序遍歷（寬度優先遍歷）
* 特點是先進先出，符合隊列的特性
*
* @param root
* @return
*/
public static List<Integer> layerOrderTraverse(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<BinaryTreeNode> 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;
}先來個結論及說明：
僅一個先（中、后）序序列不能構造唯一一顆二叉樹（原因：無法確定左右子樹或根結點）
僅先（后）序序列和中序序列可以構造唯一一顆二叉樹（原因：先序序列和后序序列無法構造唯一一顆二叉樹）
用擴充先（后）序序列可以構造唯一一顆二叉樹
用擴充中序序列不能構造唯一一顆二叉樹
實現：
/**
* 根據先序序列和中序序列構造二叉樹（遞歸實現）
* <p>
* 先序序列第一個元素是樹的根結點，從中序序列中找出與根結點所在位置k:
* 1.確定根結點的左子樹和右子樹的中序序列：該位置之前的元素就是根結點左子樹的中序序列，該位置之后的元素就是根結點的右子樹的中序序列
* 2.確定根結點的左子樹和右子樹的先序序列：先序序列第一個元素往后k元素就是根結點左子樹的先序序列，k+1位置之后就是根結點右子樹的先序序列
* <p>
* <p>
* 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;
}一個節點的左子樹和右子樹存在三種組合方式，左子樹為null，右子樹為null，左右子樹都不為null。 運用遞歸思想時，按這三種情況分析左右子樹的后序序列和中序序列。實現如下：
/**
* 根據后序序列和中序序列構造二叉樹（遞歸實現）
*
* 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;
}
//左子樹個數
int countLeft = k - s;
//右子樹個數
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實現二叉樹的遍歷方法是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
