Java中二叉樹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)示例
來(lái)看一個(gè)具體的習(xí)題實(shí)踐:
題目
根據(jù)二叉樹前序遍歷序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,構(gòu)建二叉樹,并且用前序、中序、后序進(jìn)行遍歷
代碼
import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 靜態(tài)內(nèi)部類,定義二叉樹節(jié)點(diǎn) */ static class TreeNode { public String data; TreeNode lchild; TreeNode rchild; public TreeNode(String x) { this.data = x; } } /** * 根據(jù)前序序列遞歸構(gòu)建二叉樹 * * @return */ public static TreeNode createBtree() { TreeNode root = null; if (count >= str.length || str[count++].equals("#")) { root = null; } else { root = new TreeNode(str[count - 1]); root.lchild = createBtree(); root.rchild = createBtree(); } return root; } /** * 前序遍歷 * * @param root */ public static void preTraverse(TreeNode root) { if (root != null) { System.out.print(root.data + " "); preTraverse(root.lchild); preTraverse(root.rchild); } } /** * 中序遍歷 * * @param root */ public static void inTraverse(TreeNode root) { if (root != null) { inTraverse(root.lchild); System.out.print(root.data + " "); inTraverse(root.rchild); } } /** * 后序遍歷 * * @param root */ public static void postTraverse(TreeNode root) { if (root != null) { postTraverse(root.lchild); postTraverse(root.rchild); System.out.print(root.data + " "); } } public static void main(String args[]) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { String s = cin.nextLine(); str = s.split(","); count = 0; TreeNode root = createBtree(); // 前序遍歷 preTraverse(root); System.out.println(); // 中序遍歷 inTraverse(root); System.out.println(); // 后序遍歷 postTraverse(root); System.out.println(); } } }
二叉樹的深度
下面是是實(shí)現(xiàn)二叉樹的遞歸算法的實(shí)現(xiàn),其思想就是,若為空,則其深度為0,否則,其深度等于左子樹和右子樹的深度的最大值加1:
class Node{ String name; Node left; Node right; public Node(String name) { this.name = name; } @Override public String toString() { return name; } } //定義二叉樹 class BinaryTree{ Node root; public BinaryTree(){ root = null; } //為了方便起見,我就直接寫個(gè)初始化的二叉樹,詳細(xì)的可以見以前的日志 public void initTree(){ Node node1 = new Node("a"); Node node2 = new Node("b"); Node node3 = new Node("c"); Node node4 = new Node("d"); Node node5 = new Node("e"); root = node1; node1.left = node2; node2.right = node3; node1.right = node4; node3.left = node5; } //求二叉樹的深度 int length(Node root){ int depth1; int depth2; if(root == null) return 0; //左子樹的深度 depth1 = length(root.right); //右子樹的深度 depth2 = length(root.left); if(depth1>depth2) return depth1+1; else return depth2+1; } } public class TestMatch{ public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.initTree(); System.out.println(tree.length(tree.root)); } }
- 圖解二叉樹的三種遍歷方式及java實(shí)現(xiàn)代碼
- 圖解紅黑樹及Java進(jìn)行紅黑二叉樹遍歷的方法
- java實(shí)現(xiàn)二叉樹的創(chuàng)建及5種遍歷方法(總結(jié))
- Java實(shí)現(xiàn)二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法示例
- Java實(shí)現(xiàn)求二叉樹的深度和寬度
- Java實(shí)現(xiàn)打印二叉樹所有路徑的方法
- java使用歸并刪除法刪除二叉樹中節(jié)點(diǎn)的方法
- JAVA 實(shí)現(xiàn)二叉樹(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))
- java實(shí)現(xiàn)二叉樹遍歷的三種方式
- 一篇文章徹底弄懂Java中二叉樹
相關(guān)文章
Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆的原理及實(shí)現(xiàn)詳解
在計(jì)算機(jī)科學(xué)中,堆(heap)?的實(shí)現(xiàn)是一種基于樹的特殊的數(shù)據(jù)結(jié)構(gòu),它可以在數(shù)組上構(gòu)建出樹的結(jié)構(gòu)體,并滿足堆的屬性。本文就來(lái)和大家詳細(xì)聊聊Java數(shù)據(jù)結(jié)構(gòu)中的堆,感興趣的可以了解一下2022-09-09Java集合中的fail-fast(快速失敗)機(jī)制詳解
這篇文章主要給大家介紹了關(guān)于Java集合中fail-fast(快速失敗)機(jī)制的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02Java多線程鎖機(jī)制相關(guān)原理實(shí)例解析
這篇文章主要介紹了Java多線程鎖機(jī)制相關(guān)原理實(shí)例解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08Java找不到或無(wú)法加載主類及編碼錯(cuò)誤問題的解決方案
今天小編就為大家分享一篇關(guān)于Java找不到或無(wú)法加載主類及編碼錯(cuò)誤問題的解決方案,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2019-02-02Spring Boot 如何使用Liquibase 進(jìn)行數(shù)據(jù)庫(kù)遷移(操作方法)
在Spring Boot應(yīng)用程序中使用Liquibase進(jìn)行數(shù)據(jù)庫(kù)遷移是一種強(qiáng)大的方式來(lái)管理數(shù)據(jù)庫(kù)模式的變化,本文重點(diǎn)講解如何在Spring Boot應(yīng)用程序中使用Liquibase進(jìn)行數(shù)據(jù)庫(kù)遷移,從而更好地管理數(shù)據(jù)庫(kù)模式的變化,感興趣的朋友跟隨小編一起看看吧2023-09-09