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