溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了Java如何實現二叉樹和遍歷，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
簡單理解為對于一個節點來說，最多擁有一個上級節點，同時最多具備左右兩個下級節點的數據結構。
由于很多排序算法都是基于二叉樹實現的，多叉樹也是二叉樹延伸過去的，所以二叉樹的建樹和遍歷就顯得非常重要。
一般情況是給你一個串，要求讓你以前序，中序，后序的方式建樹。那么此時我們就需要首先了解三個概念：
前序遍歷
中序遍歷
后序遍歷
我們來看看一棵二叉樹的結構：
0
1 2
3 4 5 6
0就是整個二叉樹的根節點，1就是0這個節點的左子樹，2就是0這個節點的右子樹。有了這個知識，我們就可以理解前中后序遍歷這個位置屬性就是指的根在哪個位置，前序遍歷就是根在前，所以就是根左子樹右子樹的遍歷方式；中序遍歷就是根在中間，所以就是左子樹根右子樹的遍歷方式；后序遍歷就是根在最后，所以就是左子樹右子樹根的遍歷方式。
遍歷的方式有三種，對應的建樹方式有已知中序和前序建樹，已知中序和后序建樹，已知前序和后序建樹三種。
如果我們僅僅是想構建一棵二叉平衡樹，可以簡單使用某一種序列建樹。用偽代碼表示這三種遍歷方式就是
1.前序遍歷的方式建樹
new Tree(根節點); buildTree(左子樹); buildTree(右子樹);
2.中序遍歷的方式建樹
buildTree(左子樹); new Tree(根節點); buildTree(右子樹);
3.后序遍歷的方式建樹
buildTree(左子樹); buildTree(右子樹); new Tree(根節點);
我們現在以序列 1, 2, 3, 4, 5, 6, 7, 8, 9 為例，如果是前序建樹方式，那么二叉樹的結構應該為：
實現也比較簡單
package com.chaojilaji.book.tree;
import com.chaojilaji.auto.autocode.utils.Json;
public class Handle {
/**
* 前序建樹
*
* @param input
* @param index
* @return
*/
public static Tree buildTreePrologue(int[] input, int index) {
// TODO: 2022/1/12 根節點就是當前index這個節點
Tree tree = new Tree();
tree.setValue(input[index]);
// TODO: 2022/1/12 左右兩個節點分別為 2*index-1和2*index+1
int[] children = new int[]{2 * index + 1, 2 * index + 2};
if (children[0] < input.length) {
tree.setLeftChild(buildTreePrologue(input, children[0]));
}
if (children[1] < input.length) {
tree.setRightChild(buildTreePrologue(input, children[1]));
}
return tree;
}
public static void demo() {
int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
Tree tree = buildTreePrologue(a, 0);
System.out.println(Json.toJson(tree));
}
public static void main(String[] args) {
demo();
}
}執行結果如下：
{
"value": 1,
"left_child": {
"value": 2,
"left_child": {
"value": 4,
"left_child": {
"value": 8,
"left_child": null,
"right_child": null
},
"right_child": {
"value": 9,
"left_child": null,
"right_child": null
}
},
"right_child": {
"value": 5,
"left_child": null,
"right_child": null
}
},
"right_child": {
"value": 3,
"left_child": {
"value": 6,
"left_child": null,
"right_child": null
},
"right_child": {
"value": 7,
"left_child": null,
"right_child": null
}
}
}以 1，2，3，4，5，6，7序列為例，如果是中序建樹的方式，那么二叉樹的結構應該為
代碼如下：
package com.chaojilaji.book.tree;
import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.auto.autocode.utils.MathUtils;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
public class Handle {
/**
* 中序建樹
* @param input
* @param height
* @param maxHeight
* @return
*/
public static Tree buildTree2(Queue<Integer> input, int height, int maxHeight) {
// TODO: 2022/1/12 根節點就是當前index這個節點
Tree tree = new Tree();
if (height < maxHeight) {
tree.setLeftChild(buildTree2(input, height + 1, maxHeight));
}
if (!input.isEmpty()) {
tree.setValue(input.poll());
}
if (height < maxHeight) {
tree.setRightChild(buildTree2(input, height + 1, maxHeight));
}
return tree;
}
public static void demo() {
int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < a.length; i++) {
queue.add(a[i]);
}
Integer maxCeng = new Double(Math.ceil(MathUtils.getLogAN(2, a.length + 1))).intValue();
System.out.println(Json.toJson(buildTree2(queue, 1, maxCeng)));
}
public static void main(String[] args) {
demo();
}
}相對前序建樹以擴展的方式建立二叉樹，中序建樹由于無法很好的控制索引，所以這里使用了一個隊列來存儲整個序列，同時需要算出以當前的節點數，算出建立一棵二叉平衡樹，最小的深度為多少。然后按照之前給出的偽代碼，按照左根右的方式賦值和遞歸調用即可。
運行的結果如下：
{
"value": 4,
"left_child": {
"value": 2,
"left_child": {
"value": 1,
"left_child": null,
"right_child": null
},
"right_child": {
"value": 3,
"left_child": null,
"right_child": null
}
},
"right_child": {
"value": 6,
"left_child": {
"value": 5,
"left_child": null,
"right_child": null
},
"right_child": {
"value": 7,
"left_child": null,
"right_child": null
}
}
}有了中序遍歷，其實后序遍歷就非常簡單了，以序列1,2,3,4,5,6,7為例，建樹應該為
代碼如下：
package com.chaojilaji.book.tree;
import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.auto.autocode.utils.MathUtils;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
public class Handle {
/**
* 后序建樹
*
* @return
*/
public static Tree buildTree3(Queue<Integer> input, int height, int maxHeight) {
// TODO: 2022/1/12 根節點就是當前index這個節點
Tree tree = new Tree();
if (height < maxHeight) {
tree.setLeftChild(buildTree3(input, height + 1, maxHeight));
}
if (height < maxHeight) {
tree.setRightChild(buildTree3(input, height + 1, maxHeight));
}
if (!input.isEmpty()) {
tree.setValue(input.poll());
}
return tree;
}
public static void demo() {
int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < a.length; i++) {
queue.add(a[i]);
}
Integer maxCeng = new Double(Math.ceil(MathUtils.getLogAN(2, a.length + 1))).intValue();
System.out.println(Json.toJson(buildTree3(queue, 1, maxCeng)));
}
public static void main(String[] args) {
demo();
}
}通過分析三個建樹方法的代碼你可以發現，其實本質上，根賦值代碼，與調用左右子樹建樹函數的擺放的位置不同，就早就了這三種不同的算法。
三種建樹方法對應的三種遍歷方法本質區別也就是打印值語句與調用左右子樹打印值函數的擺放位置不同。如果舉一反三的話，我們可以很容易的得出二叉樹前中后序遍歷的代碼。那么，請你自己先嘗試一下。
根據建樹的經驗，知道，我們只需要寫出一種遍歷方法，那么其他兩種遍歷方式都有了。區別只不過是換換打印語句的位置。
對于前序遍歷，寫法如下：
public static void print1(Tree tree) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getValue())) {
System.out.print(tree.getValue());
}
if (Objects.nonNull(tree.getLeftChild())) {
print1(tree.getLeftChild());
}
if (Objects.nonNull(tree.getRightChild())) {
print1(tree.getRightChild());
}
}那么我們來做一個實驗，首先根據序列1,2,3,4,5,6,7利用前序遍歷構建出一棵平衡二叉樹，然后打印出其前序中序后序遍歷的順序。完整的代碼如下：
package com.chaojilaji.book.tree;
import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.auto.autocode.utils.MathUtils;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
public class Handle {
/**
* 前序建樹
*
* @param input
* @param index
* @return
*/
public static Tree buildTreePrologue(int[] input, int index) {
// TODO: 2022/1/12 根節點就是當前index這個節點
Tree tree = new Tree();
tree.setValue(input[index]);
// TODO: 2022/1/12 左右兩個節點分別為 2*index-1和2*index+1
int[] children = new int[]{2 * index + 1, 2 * index + 2};
if (children[0] < input.length) {
tree.setLeftChild(buildTreePrologue(input, children[0]));
}
if (children[1] < input.length) {
tree.setRightChild(buildTreePrologue(input, children[1]));
}
return tree;
}
/**
* 中序建樹
*
* @param input
* @param height
* @param maxHeight
* @return
*/
public static Tree buildTree2(Queue<Integer> input, int height, int maxHeight) {
// TODO: 2022/1/12 根節點就是當前index這個節點
Tree tree = new Tree();
if (height < maxHeight) {
tree.setLeftChild(buildTree2(input, height + 1, maxHeight));
}
if (!input.isEmpty()) {
tree.setValue(input.poll());
}
if (height < maxHeight) {
tree.setRightChild(buildTree2(input, height + 1, maxHeight));
}
return tree;
}
/**
* 后序建樹
*
* @return
*/
public static Tree buildTree3(Queue<Integer> input, int height, int maxHeight) {
// TODO: 2022/1/12 根節點就是當前index這個節點
Tree tree = new Tree();
if (height < maxHeight) {
tree.setLeftChild(buildTree3(input, height + 1, maxHeight));
}
if (height < maxHeight) {
tree.setRightChild(buildTree3(input, height + 1, maxHeight));
}
if (!input.isEmpty()) {
tree.setValue(input.poll());
}
return tree;
}
public static void print1(Tree tree) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getValue())) {
System.out.print(tree.getValue());
}
if (Objects.nonNull(tree.getLeftChild())) {
print1(tree.getLeftChild());
}
if (Objects.nonNull(tree.getRightChild())) {
print1(tree.getRightChild());
}
}
public static void print2(Tree tree) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getLeftChild())) {
print2(tree.getLeftChild());
}
if (Objects.nonNull(tree.getValue())) {
System.out.print(tree.getValue());
}
if (Objects.nonNull(tree.getRightChild())) {
print2(tree.getRightChild());
}
}
public static void print3(Tree tree) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getLeftChild())) {
print3(tree.getLeftChild());
}
if (Objects.nonNull(tree.getRightChild())) {
print3(tree.getRightChild());
}
if (Objects.nonNull(tree.getValue())) {
System.out.print(tree.getValue());
}
}
public static void demoPrint() {
int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
Tree tree = buildTreePrologue(a, 0);
print1(tree);
System.out.println();
print2(tree);
System.out.println();
print3(tree);
}
public static void main(String[] args) {
demoPrint();
}
}最終的結果如下：
感謝你能夠認真閱讀完這篇文章，希望小編分享的“Java如何實現二叉樹和遍歷”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
