建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
本篇內(nèi)容主要講解“java樹(shù)的存儲(chǔ)結(jié)構(gòu)以及二叉樹(shù)的遍歷實(shí)現(xiàn)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“java樹(shù)的存儲(chǔ)結(jié)構(gòu)以及二叉樹(shù)的遍歷實(shí)現(xiàn)”吧!
創(chuàng)新互聯(lián)建站專(zhuān)注于關(guān)嶺企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站建設(shè),電子商務(wù)商城網(wǎng)站建設(shè)。關(guān)嶺網(wǎng)站建設(shè)公司,為關(guān)嶺等地區(qū)提供建站服務(wù)。全流程按需定制開(kāi)發(fā)，專(zhuān)業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)建站專(zhuān)業(yè)和態(tài)度為您提供的服務(wù)
樹(shù)的存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)中定義的樹(shù)，類(lèi)似于下圖：
前面我們說(shuō)過(guò)，計(jì)算機(jī)只能順序或者鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)，所以樹(shù)這樣的結(jié)構(gòu)是不能直接存儲(chǔ)的，所以要將其轉(zhuǎn)換為順序或鏈?zhǔn)絹?lái)存儲(chǔ)。主要有以下三種方式：
雙親表示法
這一方法基于數(shù)組，也基于樹(shù)的每個(gè)結(jié)點(diǎn)（除了根結(jié)點(diǎn)）都有且僅有一個(gè)父結(jié)點(diǎn)。做法是存儲(chǔ)每個(gè)結(jié)點(diǎn)時(shí)，增加一個(gè)域指向其父結(jié)點(diǎn)的位置。比如上圖，按照雙親表示法存儲(chǔ)在數(shù)組中，結(jié)構(gòu)就是這樣的：
實(shí)際操作時(shí)，就是從上往下，層序遍歷一棵樹(shù)，并為相應(yīng)的域賦值即可。這種存儲(chǔ)方式，可以快速獲取任意結(jié)點(diǎn)的父結(jié)點(diǎn)位置，但相反的操作，要獲取一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)，就需要遍歷了。
但是以上問(wèn)題可以通過(guò)增加一個(gè)域來(lái)解決，可以增加一個(gè)firstChild域，表示一個(gè)結(jié)點(diǎn)最左邊的子結(jié)點(diǎn)，例如對(duì)于以上這棵樹(shù)，A的firstChild是B，B的firstChild是D。這樣我們就可以得到任何一個(gè)結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)了，而所有的子結(jié)點(diǎn)又是連續(xù)的，所以就可以方便的獲取到所有的子結(jié)點(diǎn)。
這引發(fā)了我們的思考，是不是通過(guò)增加域，我們可以獲取任何想要的關(guān)系？比如可以存儲(chǔ)兄弟結(jié)點(diǎn)的位置。是的，這是很靈活的，但是也要注意設(shè)計(jì)合理，過(guò)于龐大的數(shù)據(jù)單元，會(huì)占用大量?jī)?nèi)存空間，這就仁者見(jiàn)仁，智者見(jiàn)智了。
孩子表示法
這一方式，是建立多個(gè)指針域，指向它所有子結(jié)點(diǎn)的地址。也就是任何一個(gè)結(jié)點(diǎn)，都掌握它所有子結(jié)點(diǎn)的信息。我們使用數(shù)組+鏈表的方式來(lái)實(shí)現(xiàn)。以上這棵樹(shù)使用孩子表示法示意結(jié)構(gòu)如下：
這樣對(duì)任何一個(gè)結(jié)點(diǎn)，都可以直接找到它的全部子結(jié)點(diǎn)了。我們還可以把它和上述的雙親表示法結(jié)合起來(lái)，以賦予它更多的能力。
孩子兄弟表示法
這種方式，可以把一棵普通的樹(shù)，轉(zhuǎn)換成二叉樹(shù)。它的做法是用兩個(gè)指針?lè)謩e指向它的第一個(gè)子結(jié)點(diǎn)和它的第一個(gè)右兄弟結(jié)點(diǎn)。
文章開(kāi)始處的這棵樹(shù)，用孩子兄弟表示法結(jié)果如下所示：
滿(mǎn)二叉樹(shù)與完全二叉樹(shù)
之前的文章里介紹了二叉樹(shù)的概念，其實(shí)二叉樹(shù)中還有幾種特殊的二叉樹(shù)，這里介紹兩種。
滿(mǎn)二叉樹(shù)
在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上，這樣的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。
滿(mǎn)二叉樹(shù)是一棵完美的二叉樹(shù)，它的每一棵子樹(shù)都是左右對(duì)稱(chēng)的。如下就是一棵滿(mǎn)二叉樹(shù)：
完全二叉樹(shù)
對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i (1≤i≤n) 的結(jié)點(diǎn)與同樣深度的滿(mǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中位置完全相同，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。
這句話(huà)可能說(shuō)的不太好理解，簡(jiǎn)單來(lái)說(shuō)，完全二叉樹(shù)就是滿(mǎn)二叉樹(shù)少幾個(gè)葉子，而且葉子是從右向左少的。比如下圖就是一棵完全二叉樹(shù)，把它和上方的滿(mǎn)二叉樹(shù)對(duì)比可以發(fā)現(xiàn)，從上往下一層一層數(shù)過(guò)去，它們是一模一樣的，僅在最后完全二叉樹(shù)缺少幾個(gè)葉子。如果中間有任何一個(gè)結(jié)點(diǎn)對(duì)應(yīng)不上，它就不是一棵完全二叉樹(shù)。
二叉樹(shù)的存儲(chǔ)
二叉樹(shù)也可以順序或鏈?zhǔn)酱鎯?chǔ)，鏈?zhǔn)酱鎯?chǔ)和樹(shù)的孩子表示法差不多，定義一個(gè)lchild和rchild指針?lè)謩e指向左孩子和右孩子即可。它的順序存儲(chǔ)卻比普通的樹(shù)要簡(jiǎn)單的多，接下來(lái)我們看下二叉樹(shù)的順序存儲(chǔ)是如何實(shí)現(xiàn)的。
順序存儲(chǔ)
以上述完全二叉樹(shù)為例，可以發(fā)現(xiàn)每個(gè)結(jié)點(diǎn)的位置和它在線(xiàn)性表中的位置是一樣的，所以不需要指針指向它的父結(jié)點(diǎn)或者子結(jié)點(diǎn)，我們直接按照層序遍歷方式把它存儲(chǔ)在數(shù)組中即可。結(jié)果如下：
以上是針對(duì)完全二叉樹(shù)而言，那如果不是一棵完全二叉樹(shù)呢？比如以下這棵樹(shù)：
從第三行開(kāi)始，數(shù)據(jù)的位置和存儲(chǔ)在數(shù)組中的位置不再一樣了，比如5在數(shù)組中的下標(biāo)是4。這時(shí)我們需要用空位補(bǔ)充，把這棵二叉樹(shù)和一棵完全二叉樹(shù)對(duì)比，缺少的部分在數(shù)組中以空或者特定的字符補(bǔ)充。以此二叉樹(shù)為例，它對(duì)應(yīng)的完全二叉樹(shù)如下，其中虛線(xiàn)連接的部分實(shí)際不存在。
然后按照完全二叉樹(shù)的方式，在數(shù)組中存儲(chǔ)時(shí)遇到實(shí)際不存在的元素就以空表示，結(jié)果如下：
這樣數(shù)組就可以正確的對(duì)應(yīng)原二叉樹(shù)了。這種方式的可行性在于，對(duì)一棵一般的二叉樹(shù)而言，可以構(gòu)造的最小的完全二叉樹(shù)是唯一的，這里最小指不在完全二叉樹(shù)結(jié)尾增加無(wú)用的葉子結(jié)點(diǎn)。
順序存儲(chǔ)的問(wèn)題也就由此暴露了，相對(duì)于完全二叉樹(shù)而言，更多的樹(shù)都是這種一般結(jié)構(gòu)，也就意味著數(shù)組中會(huì)有大量的空位，這大大的浪費(fèi)了內(nèi)存。
二叉樹(shù)的遍歷實(shí)現(xiàn)
二叉樹(shù)的遍歷分為前序、中序、后序三種，還有一種叫做層序遍歷，就是從上往下一層一層進(jìn)行遍歷。之前介紹了這幾種遍歷的概念，接下來(lái)我們以上述的一般二叉樹(shù)為樣例來(lái)演示這幾種遍歷。
1. 構(gòu)造二叉樹(shù)
我們以鏈?zhǔn)酱鎯?chǔ)方式進(jìn)行演示，結(jié)點(diǎn)的結(jié)構(gòu)如下：
class TreeNode{
Integer data;
TreeNode lChild;
TreeNode rChild;
public TreeNode(Integer data){
this.data = data;
}
}2. 層序遍歷
層序遍歷的特點(diǎn)是先獲取根結(jié)點(diǎn)的值，然后獲取它的左孩子，再獲取它的右孩子，如上方這棵樹(shù)中，獲取順序1->2->3，這部分非常簡(jiǎn)單。但下一步卻要從3回到2，獲取到5后再回到3，這樣在2和3之間來(lái)回跳躍，便不那么好處理了。我們可以借助隊(duì)列來(lái)完成。
為了便于演示，我們用黑色代表當(dāng)前結(jié)點(diǎn)，藍(lán)色代表它的左孩子，紅色代表它的右孩子，建立如下模型：
以上述樹(shù)為例，借助Queue實(shí)現(xiàn)的原理如下：
首先根結(jié)點(diǎn)入隊(duì)，入隊(duì)時(shí)，剪掉它的兩個(gè)孩子，并按照左右順序把兩個(gè)孩子都入隊(duì)，然后根結(jié)點(diǎn)丟棄：
然后對(duì)結(jié)點(diǎn)2進(jìn)行同樣的處理：
接下來(lái)處理結(jié)點(diǎn)3：
到這里相信大家已經(jīng)發(fā)現(xiàn)了，獲取到2之后下一步獲取的是3，而獲取5被巧妙的放在了3之后，這樣我們就可以一層層的遍歷二叉樹(shù)了。Java代碼如下所示：
private void levelTraverse(TreeNode tree){
if(tree == null) return;
Queue queue = new LinkedList<>();
queue.add(tree);
TreeNode node;
while (!queue.isEmpty()) {
node = queue.poll();
System.out.println("Node is " + node.data);
if(node.lChild!=null){
queue.offer(node.lChild);
}
if(node.rChild!=null){
queue.offer(node.rChild);
}
}
} 3. 前序遍歷
前序遍歷可以簡(jiǎn)單的使用遞歸實(shí)現(xiàn)，代碼一目了然，如下：
private void preOrderTraverse(TreeNode tree){
if (tree == null) {
return;
}
System.out.println("Node is " + tree.data);
preOrderTraverse(tree.lChild);
preOrderTraverse(tree.rChild);
}4. 中序遍歷
private void inOrderTraverse(TreeNode tree){
if (tree == null) {
return;
}
inOrderTraverse(tree.lChild);
System.out.println("Node is " + tree.data);
inOrderTraverse(tree.rChild);
}5. 后續(xù)遍歷
private void postOrderTraverse(TreeNode tree){
if (tree == null) {
return;
}
postOrderTraverse(tree.lChild);
postOrderTraverse(tree.rChild);
System.out.println("Node is " + tree.data);
}到此，相信大家對(duì)“java樹(shù)的存儲(chǔ)結(jié)構(gòu)以及二叉樹(shù)的遍歷實(shí)現(xiàn)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！
網(wǎng)站欄目：java樹(shù)的存儲(chǔ)結(jié)構(gòu)以及二叉樹(shù)的遍歷實(shí)現(xiàn)
文章分享：http://fisionsoft.com.cn/article/geojjs.html
