Java實(shí)現(xiàn)二叉樹的基本操作詳解
1. 二叉樹結(jié)點(diǎn)的構(gòu)成
這里采用的是孩子表示法, 所以節(jié)點(diǎn)類(使用的是靜態(tài)內(nèi)部類)中除了數(shù)值域外要有兩個(gè)引用來表示節(jié)點(diǎn)的左子樹和右子樹.
static class TreeNode {
public char val;//數(shù)值
public TreeNode left;//左子樹引用
public TreeNode right;//右子樹引用
public TreeNode(char val) {
this.val = val;
}
}
2. 二叉樹的遍歷
二叉樹的遍歷 (Traversal) 是指沿著某條搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題(比如：打印節(jié)點(diǎn)內(nèi)容、節(jié)點(diǎn)內(nèi)容加 1)。 遍歷是二叉樹上最重要的操作之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。
其實(shí)不管是前序遍歷，中序遍歷，還是后續(xù)遍歷，二叉樹的遍歷所走的路徑都是相同的，三者之間的區(qū)別只是獲取根節(jié)點(diǎn)數(shù)據(jù)的時(shí)機(jī)不同。
2.1 前序遍歷
前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)—>根的左子樹—>根的右子樹。
我們利用遞歸解決問題的思想, 可以將一個(gè)問題拆解為子問題去解決, 也就是實(shí)現(xiàn)下面的過程:
- 訪問根節(jié)點(diǎn)數(shù)據(jù)；
- 前序遍歷左子樹；
- 前序遍歷右子樹;
遞歸結(jié)束條件：如果結(jié)點(diǎn)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é)點(diǎn)—>根的右子樹;
和上面的實(shí)現(xiàn)思想相同, 只是訪問根節(jié)點(diǎn)的時(shí)機(jī)不同;
- 中序遍歷左子樹；
- 訪問根節(jié)點(diǎn)數(shù)據(jù)；
- 中序遍歷右子樹;
遞歸結(jié)束條件：如果結(jié)點(diǎn)root為空，則返回。
//中序遍歷
public void InOrder(TreeNode root) {
if(root == null) {
return;
}
InOrder(root.left);
System.out.print(root.val+" ");
InOrder(root.right);
}
2.3 后序遍歷
同樣的, 實(shí)現(xiàn)過程如下,
- 后序遍歷左子樹；
- 后序遍歷右子樹；
- 訪問根結(jié)點(diǎn)數(shù)據(jù);
遞歸結(jié)束條件：如果結(jié)點(diǎn)root為空，則返回。
//后序遍歷
public void postOrder(TreeNode root) {
if(root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}
3. 獲取整棵二叉樹的節(jié)點(diǎn)個(gè)數(shù)
獲取樹中的節(jié)點(diǎn)個(gè)數(shù), 最容易想到的就是遍歷一遍樹, 通過計(jì)數(shù)實(shí)現(xiàn)了, 代碼寫起來也不難;
也可以通過遞歸解決子問題的思想來實(shí)現(xiàn) , 本質(zhì)上還是在遍歷二叉樹
節(jié)點(diǎn)的個(gè)數(shù)等于根節(jié)點(diǎn)(1) + 左子樹節(jié)點(diǎn)個(gè)數(shù) + 右子樹節(jié)點(diǎn)個(gè)數(shù) ,
遞歸結(jié)束條件: 如果結(jié)點(diǎn)root為空，則返回。
//獲取樹中節(jié)點(diǎn)的個(gè)數(shù),遍歷計(jì)數(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é)點(diǎn)的個(gè)數(shù),子問題思想
public int size2(TreeNode root) {
if(root == null) {
return 0;
}
return size2(root.left) + size2(root.right) + 1;
}
4. 獲取二叉樹葉子節(jié)點(diǎn)的個(gè)數(shù)
同樣的思考的話和上面一樣, 可以采用計(jì)數(shù)和子問題來實(shí)現(xiàn), 不過本質(zhì)上是差不多的;
遞歸思路：
- 如果結(jié)點(diǎn)為空，表示該樹沒有結(jié)點(diǎn)返回0，
- 如果結(jié)點(diǎn)的左右子樹都為空，表示該結(jié)點(diǎn)為葉子結(jié)點(diǎn)，計(jì)算器+1或者返回1。
- 一棵二叉樹的葉子結(jié)點(diǎn)數(shù)為左右子樹葉子結(jié)點(diǎn)數(shù)之和。
//獲取葉子節(jié)點(diǎn)的個(gè)數(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é)點(diǎn)的個(gè)數(shù),遍歷計(jì)數(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é)點(diǎn)的個(gè)數(shù)
遞歸思路：
- 如果結(jié)點(diǎn)為空，返回0，k為1，返回1。
- 一棵二叉樹第k層結(jié)點(diǎn)數(shù)為 左子樹和右子樹第k-1層次的結(jié)點(diǎn)數(shù)之和。
當(dāng)k=1時(shí)，表示第一層次的結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)個(gè)數(shù)為1，每遞歸一層，從根節(jié)點(diǎn)來說是第k層, 那么相對于根節(jié)點(diǎn)的子樹來說就是k-1層，所以一棵二叉樹第k層結(jié)點(diǎn)數(shù)為左子樹，右子樹第k-1層次的結(jié)點(diǎn)數(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é)點(diǎn)為空，則這棵樹的高度為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. 在二叉樹中尋找目標(biāo)值
通過遍歷去搜索比較即可, 前中后序遍歷都可以.
//檢測值為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. 判斷二叉樹是不是完全二叉樹
判斷一棵樹是不是完全二叉樹，我們可以設(shè)計(jì)一個(gè)隊(duì)列來實(shí)現(xiàn)，
完全二叉樹按照從上至下, 從左到右的順序節(jié)點(diǎn)之間是連續(xù)著沒有空位置的, 這里如果有不了解的可以看一看二叉樹概念篇的博客; 如果一顆二叉樹不是完全二叉樹 , 那么樹中的節(jié)點(diǎn)之間是有空著的位置的(null); 只要找到這個(gè)位置, 后面再沒有節(jié)點(diǎn)了就是完全二叉樹; 如果空位置后面還有節(jié)點(diǎn)就不是完全二叉樹;
我們可以設(shè)計(jì)一個(gè)隊(duì)列來實(shí)現(xiàn), 首先將根節(jié)點(diǎn)入隊(duì)，然后循環(huán)每次將隊(duì)頭元素出隊(duì)同時(shí)將出隊(duì)節(jié)點(diǎn)的左右孩子結(jié)點(diǎn)（包括空結(jié)點(diǎn)）依次入隊(duì)，以此類推，直到獲取的結(jié)點(diǎn)為空(就是上面說的空位置)，此時(shí)判斷隊(duì)列中的所有元素是否為空，如果為空，就表示這棵二叉樹為完全二叉樹 ; 否則就不是完全二叉樹.
//判斷一棵樹是不是完全二叉樹
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);
}
//判斷隊(duì)列中是否有不為空的元素
int size = queue.size();
while(size != 0) {
size--;
if(queue.poll() != null) {
return false;
}
}
return true;
}9. 層序遍歷
層序遍歷的實(shí)現(xiàn)方式與判斷一棵二叉樹是否是完全二叉樹類似，都是使用隊(duì)列來進(jìn)行實(shí)現(xiàn)，只有一點(diǎn)不同, 入隊(duì)時(shí)如果結(jié)點(diǎn)為空，則不需要入隊(duì)，其他的地方完全相同, 出隊(duì)時(shí)獲取到節(jié)點(diǎn)中的元素, 直到最終隊(duì)列和當(dāng)前結(jié)點(diǎn)均為空時(shí)，表示遍歷結(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);
}
}
}到此這篇關(guān)于Java實(shí)現(xiàn)二叉樹的基本操作詳解的文章就介紹到這了,更多相關(guān)Java二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java經(jīng)典設(shè)計(jì)模式之策略模式,簡單說明了策略模式的概念、原理并結(jié)合實(shí)例形式分析了java策略模式的具有用法與相關(guān)注意事項(xiàng),需要的朋友可以參考下2021-07-07
這篇文章主要介紹了在Java SE上使用Headless模式的超級指南,文中介紹了Headless模式實(shí)際使用的各種技巧,極力推薦!需要的朋友可以參考下2015-07-07
本篇文章主要介紹了淺談Java線程Thread.join方法解析，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-01-01
Java中StringBuffer和StringBuilder區(qū)別
這篇文章主要介紹了Java中StringBuffer和StringBuilder區(qū)別,本文只介紹了它們之間的核心區(qū)別,需要的朋友可以參考下2015-06-06
SpringMVC中的DispatcherServlet結(jié)構(gòu)和初始化詳解
這篇文章主要介紹了SpringMVC中的DispatcherServlet結(jié)構(gòu)和初始化詳解,SpringMVC中Spring容器的關(guān)系是通過監(jiān)聽方式啟動的,那么Spring與Servlet的Web容器(如：Tomcat、jetty)的關(guān)系則是通過DispatcherServlet進(jìn)行關(guān)聯(lián),需要的朋友可以參考下2024-01-01
spring data jpa開啟批量插入、批量更新的問題解析
這篇文章主要介紹了spring data jpa開啟批量插入、批量更新問題，本文通過圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì),需要的朋友可以參考下2021-07-07
SpringAOP事務(wù)配置語法及實(shí)現(xiàn)過程詳解
這篇文章主要介紹了SpringAOP事務(wù)配置語法及實(shí)現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06
IDEA設(shè)置Maven自動編譯model的實(shí)現(xiàn)方法
本文主要介紹了IDEA設(shè)置Maven自動編譯model的實(shí)現(xiàn)方法, maven結(jié)構(gòu)的項(xiàng)目,我們在每次修改代碼后都會需要手動編譯,本文就可以解決這個(gè)問題,感興趣的可以了解一下2023-08-08
在本文中,將為大家展示如何利用 JxBrowser 的功能,實(shí)現(xiàn)運(yùn)行在不同電腦上的兩個(gè) Java 應(yīng)用程序之間的屏幕共享,感興趣的小伙伴可以參考一下2024-10-10
JSONObject如何轉(zhuǎn)為實(shí)體類對象
介紹了JSONObject轉(zhuǎn)為實(shí)體類對象的三種方法：JSONObject中的toJavaObject方法和getObject方法支持深轉(zhuǎn)換,而JSON中的parseObject方法只能轉(zhuǎn)換一層對象,此外,還補(bǔ)充說明了在對JSON轉(zhuǎn)為實(shí)體類對象時(shí),無論JSON中的數(shù)據(jù)字段是否多于或少于實(shí)體類中字段,轉(zhuǎn)化都不會報(bào)錯(cuò)2024-11-11