title: 二叉樹的基本知識 date: 2022-06-12 15:37:23 tags: 二叉樹 演算法 待補充 二叉樹的四種遍歷方式 不要較真，其實也可以分為兩種：廣度優先（層級）和深度優先（前序、中序、後序） 基本概念不再贅述。**複雜度：**設二叉樹中元素數目為n。這四種遍歷演算法的空間複雜 ...
title: 二叉樹的基本知識
date: 2022-06-12 15:37:23
tags:
- 二叉樹
- 演算法
- 待補充
二叉樹的四種遍歷方式
不要較真，其實也可以分為兩種：廣度優先（層級）和深度優先（前序、中序、後序）
基本概念不再贅述。複雜度：設二叉樹中元素數目為n。這四種遍歷演算法的空間複雜性均為O (n)，時間複雜性為O(n)。
二叉樹數據結構
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
1
/ \
2 5
/ \
3 4
前序遍歷
遍歷順序：根節點-> 左節點-> 右節點
代碼實現：
/**
* 前序遍歷 根 -> 左 -> 右
*/
public void preOrder(TreeNode tree){
if (tree == null){
return;
}
System.out.print(tree.val);
preOrder(tree.left);
preOrder(tree.right);
}
非遞歸方式
//java 中使用 Deque， Stack已經棄用。
//Deque 的使用用法：push、pop。
public void perOrderIter(TreeNode root){
if (root == null){
return;
}
Deque<TreeNode> stack = new ArrayDeque<>();
StringBuilder result = new StringBuilder();
stack.push(root);
while(!stack.isEmpty()){
TreeNode treeNode = stack.pop();
result.append(treeNode.val);
if (treeNode.right != null){
stack.push(treeNode.right);
}
if (treeNode.left != null){
stack.push(treeNode.left);
}
}
System.out.println(result.toString());
}
中序遍歷
遍歷順序：左節點-> 根節點-> 右節點
代碼實現
/**
* 中序遍歷 左 -> 根 -> 右
* 結果：32415
*/
public void midOrder(TreeNode tree){
if (tree == null){
return;
}
midOrder(tree.left);
System.out.print(tree.val);
midOrder(tree.right);
}
/**
* 迭代式中序遍歷 左 -> 根 -> 右
* 這個比較難，重點關註一下。
*/
public void minOrderIter(TreeNode root){
if (root == null){
return;
}
Deque<TreeNode> stack = new ArrayDeque<>();
StringBuilder result = new StringBuilder();
while(root != null || !stack.isEmpty()){
//此處的目的是放入將根節點放入，然後將根節點的左節點壓在根節點上面。
while (root != null){
stack.push(root);
root = root.left;
}
//調出棧
root = stack.pop();
result.append(root.val);
root = root.right;
}
System.out.println(result.toString());
}
後序遍歷
遍歷順序：左節點-> 右節點-> 根節點
/**
* 後序遍歷 左 -> 右 -> 根
* 結果：34251
*/
public void postOrder(TreeNode tree){
if (tree == null){
return;
}
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.val);
}
/**
* 迭代式後序遍歷
* 後序遍歷更複雜！！！！
* 先遍歷左節點 -> 右節點 -> 根節點
* 1
* / \
* 2 5
* / \
* 3 4
* / \
* 7 8
*/
public void postOrderIter(TreeNode root){
if (root == null){
return;
}
Deque<TreeNode> stack = new ArrayDeque<>();
StringBuilder result = new StringBuilder();
TreeNode pre = null; //記錄前置節點
while(root != null || !stack.isEmpty()){
//把所有的左子樹節點都放入棧中
while(root != null){
stack.push(root);
root = root.left;
}
//找到當前節點
root = stack.pop();
//如果當前節點的右節點為空
//這裡為什麼會有對pre的判斷，是為了避免重覆處理。
//拿例子：當8已經處理完了之後，應該處理4節點，當時發現4也是有右子樹的，但是8已經處理過了，通過pre達標，那麼8也不用處理。
if (root.right == null || pre == root.right){
result.append(root.val);
//設置前置節點
pre = root;
//置為空的目的是處理棧中堆積的父節點。
root = null;
} else{
//右節點非空,說明當前節點這個時候不能夠處理,就把當前節點再放回去。
stack.push(root);
//把當前節點的右節點作為root進行處理。
root = root.right;
}
}
System.out.println(result.toString());
}
層級遍歷
/**
* 層級遍歷
* 遞歸的方式
* 遞歸需要存儲每個的層級 對應的數據都有什麼，藉助額外的數據結構
*/
public List<StringBuilder> result = new ArrayList<>();
public void levelOrder(TreeNode root, int level) {
if (root == null) {
return;
}
//當數組大小等於層級時，初始化該層級需要的存儲空間
if (result.size() == level) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(root.val);
result.add(level, stringBuilder);
} else {
result.get(level).append(root.val);
}
levelOrder(root.left, level + 1);
levelOrder(root.right, level + 1);
}
/**
* 迭代式層級遍歷
* 藉助額外的數據結構：隊列，特性：先進先出
* queue 的基本用法：add(offer)，remove(poll)
*/
public void levelOrderIter(TreeNode root) {
if (root == null) {
return;
}
StringBuilder result = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode current = queue.poll();
result.append(current.val);
if (current.left != null){
queue.add(current.left);
}
if (current.right != null){
queue.add(current.right);
}
}
System.out.println(result.toString());
}
額外：
/**
* 獲取二叉樹的最大深度
*/
public int getMaxDepth(TreeNode root){
if (root == null){
return 0;
}
return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1);
}
文章作者: 馮廷鑫
文章鏈接: http://fengtingxin.github.io/2022/06/12/二叉樹的基本知識/
