Java實現(xiàn)二叉樹的基本操作詳解
1. 二叉樹結(jié)點的構成
這里采用的是孩子表示法, 所以節(jié)點類(使用的是靜態(tài)內(nèi)部類)中除了數(shù)值域外要有兩個引用來表示節(jié)點的左子樹和右子樹.
static class TreeNode {
public char val;//數(shù)值
public TreeNode left;//左子樹引用
public TreeNode right;//右子樹引用
public TreeNode(char val) {
this.val = val;
}
}
2. 二叉樹的遍歷
二叉樹的遍歷 (Traversal) 是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應用問題(比如：打印節(jié)點內(nèi)容、節(jié)點內(nèi)容加 1)。 遍歷是二叉樹上最重要的操作之一，是二叉樹上進行其它運算之基礎。
其實不管是前序遍歷，中序遍歷，還是后續(xù)遍歷，二叉樹的遍歷所走的路徑都是相同的，三者之間的區(qū)別只是獲取根節(jié)點數(shù)據(jù)的時機不同。
2.1 前序遍歷
前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點—>根的左子樹—>根的右子樹。
我們利用遞歸解決問題的思想, 可以將一個問題拆解為子問題去解決, 也就是實現(xiàn)下面的過程:
- 訪問根節(jié)點數(shù)據(jù)；
- 前序遍歷左子樹；
- 前序遍歷右子樹;
遞歸結(jié)束條件：如果結(jié)點root為空，則返回。
//前序遍歷
public void preOrder(TreeNode root) {
if(root == null) {
return;
}
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
2.2 中序遍歷
中序遍歷(Inorder Traversal)——根的左子樹—>根節(jié)點—>根的右子樹;
和上面的實現(xiàn)思想相同, 只是訪問根節(jié)點的時機不同;
- 中序遍歷左子樹；
- 訪問根節(jié)點數(shù)據(jù)；
- 中序遍歷右子樹;
遞歸結(jié)束條件：如果結(jié)點root為空，則返回。
//中序遍歷
public void InOrder(TreeNode root) {
if(root == null) {
return;
}
InOrder(root.left);
System.out.print(root.val+" ");
InOrder(root.right);
}
2.3 后序遍歷
同樣的, 實現(xiàn)過程如下,
- 后序遍歷左子樹；
- 后序遍歷右子樹；
- 訪問根結(jié)點數(shù)據(jù);
遞歸結(jié)束條件：如果結(jié)點root為空，則返回。
//后序遍歷
public void postOrder(TreeNode root) {
if(root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}
3. 獲取整棵二叉樹的節(jié)點個數(shù)
獲取樹中的節(jié)點個數(shù), 最容易想到的就是遍歷一遍樹, 通過計數(shù)實現(xiàn)了, 代碼寫起來也不難;
也可以通過遞歸解決子問題的思想來實現(xiàn) , 本質(zhì)上還是在遍歷二叉樹
節(jié)點的個數(shù)等于根節(jié)點(1) + 左子樹節(jié)點個數(shù) + 右子樹節(jié)點個數(shù) ,
遞歸結(jié)束條件: 如果結(jié)點root為空，則返回。
//獲取樹中節(jié)點的個數(shù),遍歷計數(shù)法
public static int nodeSize;
public int size(TreeNode root) {
//先將nodeSzie置為0
nodeSize = 0;
sizefunc(root);
return nodeSize;
}
public void sizefunc(TreeNode root) {
if(root == null) {
return;
}
nodeSize++;
sizefunc(root.left);
sizefunc(root.right);
}
//獲取樹中節(jié)點的個數(shù),子問題思想
public int size2(TreeNode root) {
if(root == null) {
return 0;
}
return size2(root.left) + size2(root.right) + 1;
}
4. 獲取二叉樹葉子節(jié)點的個數(shù)
同樣的思考的話和上面一樣, 可以采用計數(shù)和子問題來實現(xiàn), 不過本質(zhì)上是差不多的;
遞歸思路：
- 如果結(jié)點為空，表示該樹沒有結(jié)點返回0，
- 如果結(jié)點的左右子樹都為空，表示該結(jié)點為葉子結(jié)點，計算器+1或者返回1。
- 一棵二叉樹的葉子結(jié)點數(shù)為左右子樹葉子結(jié)點數(shù)之和。
//獲取葉子節(jié)點的個數(shù),子問題思想
public int getLeafNodeCount(TreeNode root){
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
//獲取葉子節(jié)點的個數(shù),遍歷計數(shù)法
public static int leafSize;
public int getLeafNodeCount2(TreeNode root){
leafSize = 0;
getLeafNodeCount2func(root);
return leafSize;
}
public void getLeafNodeCount2func(TreeNode root) {
if(root == null) {
return;
}
if(root.left == null && root.right == null) {
leafSize++;
}
getLeafNodeCount2func(root.left);
getLeafNodeCount2func(root.right);
}
5. 獲取第K層節(jié)點的個數(shù)
遞歸思路：
- 如果結(jié)點為空，返回0，k為1，返回1。
- 一棵二叉樹第k層結(jié)點數(shù)為 左子樹和右子樹第k-1層次的結(jié)點數(shù)之和。
當k=1時，表示第一層次的結(jié)點個數(shù)，結(jié)點個數(shù)為1，每遞歸一層，從根節(jié)點來說是第k層, 那么相對于根節(jié)點的子樹來說就是k-1層，所以一棵二叉樹第k層結(jié)點數(shù)為左子樹，右子樹第k-1層次的結(jié)點數(shù)之和。
public int getKLevelNodeCount(TreeNode root, int k) {
if(root == null || k <= 0) {
return 0;
}
if(k == 1) {
return 1;
}
return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
}
6. 獲取二叉樹的高度(深度)
遞歸思路：
如果根結(jié)點為空，則這棵樹的高度為0，返回0。
一棵二叉樹的最深深度即為左右子樹深度的最大值加上1。
// 獲取二叉樹的高度
public int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftHight = getHeight(root.left);
int rightHight = getHeight(root.right);
return leftHight>rightHight ? leftHight+1 : rightHight+1;
}
7. 在二叉樹中尋找目標值
通過遍歷去搜索比較即可, 前中后序遍歷都可以.
//檢測值為val的元素是否存在
public boolean find(TreeNode root, char val) {
if(root == null) {
return false;
}
if(root.val == val) {
return true;
}
boolean ret1 = find(root.left, val);
if(ret1){
return true;
}
boolean ret2 = find(root.right, val);
if(ret2){
return true;
}
return false;
}8. 判斷二叉樹是不是完全二叉樹
判斷一棵樹是不是完全二叉樹，我們可以設計一個隊列來實現(xiàn)，
完全二叉樹按照從上至下, 從左到右的順序節(jié)點之間是連續(xù)著沒有空位置的, 這里如果有不了解的可以看一看二叉樹概念篇的博客; 如果一顆二叉樹不是完全二叉樹 , 那么樹中的節(jié)點之間是有空著的位置的(null); 只要找到這個位置, 后面再沒有節(jié)點了就是完全二叉樹; 如果空位置后面還有節(jié)點就不是完全二叉樹;
我們可以設計一個隊列來實現(xiàn), 首先將根節(jié)點入隊，然后循環(huán)每次將隊頭元素出隊同時將出隊節(jié)點的左右孩子結(jié)點（包括空結(jié)點）依次入隊，以此類推，直到獲取的結(jié)點為空(就是上面說的空位置)，此時判斷隊列中的所有元素是否為空，如果為空，就表示這棵二叉樹為完全二叉樹 ; 否則就不是完全二叉樹.
//判斷一棵樹是不是完全二叉樹
public boolean isCompleteTree(TreeNode root) {
if(root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur == null) {
break;
}
queue.offer(cur.left);
queue.offer(cur.right);
}
//判斷隊列中是否有不為空的元素
int size = queue.size();
while(size != 0) {
size--;
if(queue.poll() != null) {
return false;
}
}
return true;
}9. 層序遍歷
層序遍歷的實現(xiàn)方式與判斷一棵二叉樹是否是完全二叉樹類似，都是使用隊列來進行實現(xiàn)，只有一點不同, 入隊時如果結(jié)點為空，則不需要入隊，其他的地方完全相同, 出隊時獲取到節(jié)點中的元素, 直到最終隊列和當前結(jié)點均為空時，表示遍歷結(jié)束。
//層序遍歷
public void levelOrder(TreeNode root) {
if(root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
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);
}
}
}到此這篇關于Java實現(xiàn)二叉樹的基本操作詳解的文章就介紹到這了,更多相關Java二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
詳解Java如何實現(xiàn)在PDF中插入,替換或刪除圖像
圖文并茂的內(nèi)容往往讓人看起來更加舒服，如果只是文字內(nèi)容的累加，往往會使讀者產(chǎn)生視覺疲勞。搭配精美的文章配圖則會使文章內(nèi)容更加豐富。那我們要如何在PDF中插入、替換或刪除圖像呢？別擔心，今天為大家介紹一種高效便捷的方法2023-01-01
Mybatis-Plus?sum聚合函數(shù)及按日期查詢并求和的方式詳解
這篇文章主要介紹了Mybatis-Plus sum聚合函數(shù)及按日期查詢并求和,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
static關鍵字基本概念我們可以一句話來概括:方便在沒有創(chuàng)建對象的情況下來進行調(diào)用。也就是說:被static關鍵字修飾的不需要創(chuàng)建對象去調(diào)用,直接根據(jù)類名就可以去訪問，讓我們來了解一下你可能還不知道情況2022-05-05
這篇文章主要介紹了詳解配置類為什么要添加@Configuration注解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
本文主要介紹了如何將java或javaweb項目打包為jar包或war包，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
這篇文章主要介紹了MyBatis找不到mapper文件的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-10-10
為了數(shù)據(jù)安全問題,有時候需要將部分敏感字段加密后再入庫，本文主要介紹了MyBatis實現(xiàn)字段加解密的實踐，具有一定的參考價值，感興趣的可以了解一下2023-11-11
這篇文章主要為大家詳細介紹了Java項目實現(xiàn)尋找迷宮出路，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
基于Java class對象說明、Java 靜態(tài)變量聲明和賦值說明(詳解)
下面小編就為大家?guī)硪黄贘ava class對象說明、Java 靜態(tài)變量聲明和賦值說明(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要介紹了Java防止文件被篡改之文件校驗功能，本文給大家分享了文件校驗和原理及具體實現(xiàn)思路,需要的朋友可以參考下2018-11-11