Java實現(xiàn)二叉樹的示例代碼(遞歸&迭代)
更新時間：2022年03月17日 15:24:42 作者：愛干飯的猿
二叉樹（Binary?tree）是樹形結(jié)構(gòu)的一個重要類型。本文將利用Java語言實現(xiàn)二叉樹，文中的示例代碼講解詳細，需要的同學(xué)可以參考一下
1.二叉樹基本概念見上節(jié)：詳解Java中二叉樹的基礎(chǔ)概念(遞歸&迭代)
2.本次展示鏈式存儲
以此圖為例，完整代碼如下：
//基礎(chǔ)二叉樹實現(xiàn)
//使用左右孩子表示法
import java.util.*;
import java.util.Deque;
public class myBinTree {
private static class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public static TreeNode build(){
TreeNode nodeA=new TreeNode('A');
TreeNode nodeB=new TreeNode('B');
TreeNode nodeC=new TreeNode('C');
TreeNode nodeD=new TreeNode('D');
TreeNode nodeE=new TreeNode('E');
TreeNode nodeF=new TreeNode('F');
TreeNode nodeG=new TreeNode('G');
TreeNode nodeH=new TreeNode('H');
nodeA.left=nodeB;
nodeA.right=nodeC;
nodeB.left=nodeD;
nodeB.right=nodeE;
nodeE.right=nodeH;
nodeC.left=nodeF;
nodeC.right=nodeG;
return nodeA;
}
//方法1(遞歸)
//先序遍歷: 根左右
public static void preOrder(TreeNode root){
if(root==null){
return;
}
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
//方法1(遞歸)
//中序遍歷
public static void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
//方法1(遞歸)
//后序遍歷
public static void postOrder(TreeNode root){
if(root==null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}
//方法2(迭代)
//先序遍歷 (迭代)
public static void preOrderNonRecursion(TreeNode root){
if(root==null){
return ;
}
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode cur=stack.pop();
System.out.print(cur.val+" ");
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}
}
//方法2(迭代)
//中序遍歷 (迭代)
public static void inorderTraversalNonRecursion(TreeNode root) {
if(root==null){
return ;
}
Deque<TreeNode> stack=new LinkedList<>();
// 當前走到的節(jié)點
TreeNode cur=root;
while (!stack.isEmpty() || cur!=null){
// 不管三七二十一，先一路向左走到根兒~
while (cur!=null){
stack.push(cur);
cur=cur.left;
}
// 此時cur為空，說明走到了null，此時棧頂就存放了左樹為空的節(jié)點
cur=stack.pop();
System.out.print(cur.val+" ");
// 繼續(xù)訪問右子樹
cur=cur.right;
}
}
//方法2(迭代)
//后序遍歷 (迭代)
public static void postOrderNonRecursion(TreeNode root){
if(root==null){
return;
}
Deque<TreeNode> stack=new LinkedList<>();
TreeNode cur=root;
TreeNode prev=null;
while (!stack.isEmpty() || cur!=null){
while (cur!=null){
stack.push(cur);
cur=cur.left;
}
cur=stack.pop();
if(cur.right==null || prev==cur.right){
System.out.print(cur.val+" ");
prev=cur;
cur=null;
}else {
stack.push(cur);
cur=cur.right;
}
}
}
//方法1(遞歸)
//傳入一顆二叉樹的根節(jié)點，就能統(tǒng)計出當前二叉樹中一共有多少個節(jié)點，返回節(jié)點數(shù)
//此時的訪問就不再是輸出節(jié)點值，而是計數(shù)器 + 1操作
public static int getNodes(TreeNode root){
if(root==null){
return 0;
}
return 1+getNodes(root.left)+getNodes(root.right);
}
//方法2(迭代)
//使用層序遍歷來統(tǒng)計當前樹中的節(jié)點個數(shù)
public static int getNodesNoRecursion(TreeNode root){
if(root==null){
return 0;
}
int size=0;
Deque<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
size++;
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
return size;
}
//方法1(遞歸)
//傳入一顆二叉樹的根節(jié)點，就能統(tǒng)計出當前二叉樹的葉子結(jié)點個數(shù)
public static int getLeafNodes(TreeNode root){
if(root==null){
return 0;
}
if(root.left==null && root.right==null){
return 1;
}
return getLeafNodes(root.left)+getLeafNodes(root.right);
}
//方法2(迭代)
//使用層序遍歷來統(tǒng)計葉子結(jié)點的個數(shù)
public static int getLeafNodesNoRecursion(TreeNode root){
if(root==null){
return 0;
}
int size=0;
Deque<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode cur=queue.poll();
if(cur.left==null && cur.right==null){
size++;
}
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
return size;
}
//層序遍歷
public static void levelOrder(TreeNode root) {
if(root==null){
return ;
}
// 借助隊列來實現(xiàn)遍歷過程
Deque<TreeNode> queue =new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size=queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur=queue.poll();
System.out.print(cur.val+" ");
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
}
}
//傳入一個以root為根節(jié)點的二叉樹，就能求出該樹的高度
public static int height(TreeNode root){
if(root==null){
return 0;
}
return 1+ Math.max(height(root.left),height(root.right));
}
//求出以root為根節(jié)點的二叉樹第k層的節(jié)點個數(shù)
public static int getKLevelNodes(TreeNode root,int k){
if(root==null || k<=0){
return 0;
}
if(k==1){
return 1;
}
return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);
}
//判斷當前以root為根節(jié)點的二叉樹中是否包含指定元素val，
//若存在返回true，不存在返回false
public static boolean contains(TreeNode root,char value){
if(root==null){
return false;
}
if(root.val==value){
return true;
}
return contains(root.left,value) || contains(root.right,value);
}
public static void main(String[] args) {
TreeNode root=build();
System.out.println("方法1(遞歸)：前序遍歷的結(jié)果為:");
preOrder(root);
System.out.println();
System.out.println("方法2(迭代)：前序遍歷的結(jié)果為:");
preOrderNonRecursion(root);
System.out.println();
System.out.println("方法1(遞歸)：中序遍歷的結(jié)果為:");
inOrder(root);
System.out.println();
System.out.println("方法2(迭代)：中序遍歷的結(jié)果為:");
inorderTraversalNonRecursion(root);
System.out.println();
System.out.println("方法1(遞歸)：后序遍歷的結(jié)果為:");
postOrder(root);
System.out.println();
System.out.println("方法2(迭代)：后序遍歷的結(jié)果為:");
postOrderNonRecursion(root);
System.out.println();
System.out.println();
System.out.println("層序遍歷的結(jié)果為:");
levelOrder(root);
System.out.println();
System.out.println();
System.out.println("方法1(遞歸)：當前二叉樹一共有:"+getNodes(root)+"個節(jié)點數(shù)");
System.out.println("方法2(迭代)：當前二叉樹一共有:"+getNodesNoRecursion(root)+"個節(jié)點數(shù)");
System.out.println("方法1(遞歸)：當前二叉樹一共有:"+getLeafNodes(root)+"個葉子節(jié)點數(shù)");
System.out.println("方法2(迭代)：當前二叉樹一共有:"+getLeafNodesNoRecursion(root)+"個葉子節(jié)點數(shù)");
System.out.println(contains(root,'E'));
System.out.println(contains(root,'P'));
System.out.println("當前二叉樹的高度為:"+height(root));
System.out.println("當前二叉樹第3層的節(jié)點個數(shù)為:"+getKLevelNodes(root,3));
}
}如上main引用結(jié)果如下：
到此這篇關(guān)于Java實現(xiàn)二叉樹的示例代碼(遞歸&迭代)的文章就介紹到這了,更多相關(guān)Java二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
JPA是Java Persistence API的簡稱，中文名Java持久層API，是JDK 5.0注解或XML描述對象－關(guān)系表的映射關(guān)系，并將運行期的實體對象持久化到數(shù)據(jù)庫中。本文主要介紹了JPA如何設(shè)置默認字段及其長度，感興趣的同學(xué)可以了解一下2021-12-12
Apache?POI是一個開源項目,能夠讓Java程序員讀取和寫入Microsoft?Office格式的文件,包括Excel、Word和PowerPoint等,本文詳細介紹了POI庫的安裝、結(jié)構(gòu)與功能,以及如何在Java中進行基本操作和進階應(yīng)用,需要的朋友可以參考下2024-10-10
Java表數(shù)據(jù)導(dǎo)出到Excel中的實現(xiàn)
這篇文章主要介紹了Java表數(shù)據(jù)導(dǎo)出到Excel中的實現(xiàn),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
SpringBoot項目中同時操作多個數(shù)據(jù)庫的實現(xiàn)方法
在實際項目開發(fā)中可能存在需要同時操作兩個數(shù)據(jù)庫的場景，本文主要介紹了SpringBoot項目中同時操作多個數(shù)據(jù)庫的實現(xiàn)方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
文章介紹了如何在新版IDEA中調(diào)整工具欄菜單的顯示方式,通過取消勾選設(shè)置中的某個選項,可以使菜單展開更加方便2025-01-01
這篇文章主要介紹了有關(guān)Java垃圾回收機制的知識，文中實例簡單易懂，方便大家更好的學(xué)習，有興趣的朋友可以了解下2020-06-06
本篇文章給大家通過理論原理等方便徹底分析了Java常量池的相關(guān)知識，有興趣的朋友閱讀學(xué)習下吧。2017-12-12
Spring事務(wù)有可能會提交，回滾、掛起、恢復(fù)，所以Spring事務(wù)提供了一種機制，可以讓程序員來監(jiān)聽當前Spring事務(wù)所處于的狀態(tài)，這篇文章主要介紹了Spring底層事務(wù)原理,需要的朋友可以參考下2023-02-02
這篇文章主要為大家詳細介紹了java實現(xiàn)簡易五子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-06-06
Idea為java程序添加啟動參數(shù)(含:VM?options、Program?arguments、Environme
設(shè)置啟動參數(shù)的意義就是當啟動程序時,程序會優(yōu)先讀取idea的配置參數(shù),這樣就可以不用修改配置文件,下面這篇文章主要給大家介紹了關(guān)于Idea為java程序添加啟動參數(shù)(含:VM?options、Program?arguments、Environment?variable)的相關(guān)資料,需要的朋友可以參考下2022-12-12