java數(shù)據(jù)結構之樹的示例分析
這篇文章主要介紹java數(shù)據(jù)結構之樹的示例分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
成都創(chuàng)新互聯(lián)公司專注于平鄉(xiāng)網(wǎng)站建設服務及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供平鄉(xiāng)營銷型網(wǎng)站建設，平鄉(xiāng)網(wǎng)站制作、平鄉(xiāng)網(wǎng)頁設計、平鄉(xiāng)網(wǎng)站官網(wǎng)定制、成都微信小程序服務，打造平鄉(xiāng)網(wǎng)絡公司原創(chuàng)品牌,更為您提供平鄉(xiāng)網(wǎng)站排名全網(wǎng)營銷落地服務。
樹定義和基本術語
定義
樹(Tree)是n(n≥0)個結點的有限集T，并且當n＞0時滿足下列條件：
（1）有且僅有一個特定的稱為根(Root)的結點；
（2）當n＞1時，其余結點可以劃分為m(m＞0)個互不相交的有限集T1、T2、…、Tm，每個集Ti(1≤i≤m)均為樹，且稱為樹T的子樹(SubTree)。
特別地，不含任何結點(即n＝0)的樹，稱為空樹。
如下就是一棵樹的結構：
基本術語
結點：存儲數(shù)據(jù)元素和指向子樹的鏈接，由數(shù)據(jù)元素和構造數(shù)據(jù)元素之間關系的引用組成。
孩子結點：樹中一個結點的子樹的根結點稱為這個結點的孩子結點，如圖1中的A的孩子結點有B、C、D
雙親結點：樹中某個結點有孩子結點(即該結點的度不為0)，該結點稱為它孩子結點的雙親結點，也叫前驅(qū)結點。雙親結點和孩子結點是相互的，如圖1中，A的孩子結點是B、C、D，B、C、D的雙親結點是A。
兄弟結點：具有相同雙親結點(即同一個前驅(qū))的結點稱為兄弟結點，如圖1中B、B、D為兄弟結點。
結點的度：結點所有子樹的個數(shù)稱為該結點的度，如圖1，A的度為3，B的度為2.
樹的度：樹中所有結點的度的最大值稱為樹的度，如圖1的度為3.
葉子結點：度為0的結點稱為葉子結點，也叫終端結點。如圖1的K、L、F、G、M、I、J
分支結點：度不為0的結點稱為分支結點，也叫非終端結點。如圖1的A、B、C、D、E、H
結點的層次：從根結點到樹中某結點所經(jīng)路徑的分支數(shù)稱為該結點的層次。根結點的層次一般為1(也可以自己定義為0)，這樣，其它結點的層次是其雙親結點的層次加1.
樹的深度：樹中所有結點的層次的最大值稱為該樹的深度(也就是最下面那個結點的層次)。
有序樹和無序樹：樹中任意一個結點的各子樹按從左到右是有序的，稱為有序樹，否則稱為無序樹。
樹的抽象數(shù)據(jù)類型描述
數(shù)據(jù)元素：具有相同特性的數(shù)據(jù)元素的集合。
結構關系：樹中數(shù)據(jù)元素間的結構關系由樹的定義確定。
基本操作：樹的主要操作有
（1）創(chuàng)建樹IntTree(&T)
創(chuàng)建1個空樹T。
（2）銷毀樹DestroyTree(&T)
（3）構造樹CreatTree(&T，deinition)
（4）置空樹ClearTree(&T)
將樹T置為空樹。
（5）判空樹TreeEmpty(T)
（6）求樹的深度TreeDepth(T)
（7）獲得樹根Root(T)
（8）獲取結點Value(T，cur_e，&e)
將樹中結點cur_e存入e單元中。
（9）數(shù)據(jù)賦值Assign(T，cur_e，value)
將結點value，賦值于樹T的結點cur_e中。
（10）獲得雙親Parent(T，cur_e)
返回樹T中結點cur_e的雙親結點。
（11）獲得最左孩子LeftChild(T，cur_e)
返回樹T中結點cur_e的最左孩子。
（12）獲得右兄弟RightSibling(T，cur_e)
返回樹T中結點cur_e的右兄弟。
（13）插入子樹InsertChild(&T，&p，i，c)
將樹c插入到樹T中p指向結點的第i個子樹之前。
（14）刪除子樹DeleteChild(&T，&p，i)
刪除樹T中p指向結點的第i個子樹。
（15）遍歷樹TraverseTree(T，visit())
樹的實現(xiàn)
樹是一種遞歸結構，表示方式一般有孩子表示法和孩子兄弟表示法兩種。樹實現(xiàn)方式有很多種、有可以由廣義表的遞歸實現(xiàn)，也可以有二叉樹實現(xiàn)，其中最常見的是將樹用孩子兄弟表示法轉(zhuǎn)化成二叉樹來實現(xiàn)。
下面以孩子表示法為例講一下樹的實現(xiàn)：
樹的定義和實現(xiàn)
package datastructure.tree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 樹的定義和實現(xiàn)
* @author Administrator
*
*/
public class Tree {
private Object data;
private List<Tree> childs;
public Tree(){
data = null;
childs = new ArrayList();
childs.clear();
}
public Tree(Object data) {
this.data = data;
childs = new ArrayList();
childs.clear();
}
/**
* 添加子樹
* @param tree 子樹
*/
public void addNode(Tree tree) {
childs.add(tree);
}
/**
* 置空樹
*/
public void clearTree() {
data = null;
childs.clear();
}
/**
* 求樹的深度
* 這方法還有點問題，有待完善
* @return 樹的深度
*/
public int dept() {
return dept(this);
}
/**
* 求樹的深度
* 這方法還有點問題，有待完善
* @param tree
* @return
*/
private int dept(Tree tree) {
if(tree.isEmpty()) {
return 0;
} else if(tree.isLeaf()) {
return 1;
} else {
int n = childs.size();
int[] a = new int[n];
for (int i=0; i<n; i++) {
if(childs.get(i).isEmpty()) {
a[i] = 0+1;
} else {
a[i] = dept(childs.get(i)) + 1;
}
}
Arrays.sort(a);
return a[n-1];
}
}
/**
* 返回遞i個子樹
* @param i
* @return
*/
public Tree getChild(int i) {
return childs.get(i);
}
/**
* 求第一個孩子 結點
* @return
*/
public Tree getFirstChild() {
return childs.get(0);
}
/**
* 求最后 一個孩子結點
* @return
*/
public Tree getLastChild() {
return childs.get(childs.size()-1);
}
public List<Tree> getChilds() {
return childs;
}
/**
* 獲得根結點的數(shù)據(jù)
* @return
*/
public Object getRootData() {
return data;
}
/**
* 判斷是否為空樹
* @return 如果為空，返回true,否則返回false
*/
public Boolean isEmpty() {
if(childs.isEmpty() && data == null)
return true;
return false;
}
/**
* 判斷是否為葉子結點
* @return
*/
public Boolean isLeaf() {
if(childs.isEmpty())
return true;
return false;
}
/**
* 獲得樹根
* @return 樹的根
*/
public Tree root() {
return this;
}
/**
* 設置根結點的數(shù)據(jù)
*/
public void setRootData(Object data) {
this.data = data;
}
/**
* 求結點數(shù)
* 這方法還有點問題，有待完善
* @return 結點的個數(shù)
*/
public int size() {
return size(this);
}
/**
* 求結點數(shù)
* 這方法還有點問題，有待完善
* @param tree
* @return
*/
private int size(Tree tree) {
if(tree.isEmpty()) {
return 0;
} else if(tree.isLeaf()) {
return 1;
} else {
int count = 1;
int n = childs.size();
for (int i=0; i<n; i++) {
if(!childs.get(i).isEmpty()) {
count += size(childs.get(i));
}
}
return count;
}
}
}樹的遍歷
樹的遍歷有兩種
前根遍歷
（1）.訪問根結點；
（2）.按照從左到右的次序行根遍歷根結點的第一棵子樹；
后根遍歷
（1）.按照從左到右的次序行根遍歷根結點的第一棵子樹；
（2）.訪問根結點；
Visit.Java
package datastructure.tree;
import datastructure.tree.btree.BTree;
/**
* 對結點進行操作的接口,規(guī)定樹的遍歷的類必須實現(xiàn)這個接口
* @author Administrator
*
*/
public interface Visit {
/**
* 對結點進行某種操作
* @param btree 樹的結點
*/
public void visit(BTree btree);
}order.java
package datastructure.tree;
import java.util.List;
/**
* 樹的遍歷
* @author Administrator
*
*/
public class Order {
/**
* 先根遍歷
* @param root 要的根結點
*/
public void preOrder(Tree root) {
if(!root.isEmpty()) {
visit(root);
for (Tree child : root.getChilds()) {
if(child != null) {
preOrder(child);
}
}
}
}
/**
* 后根遍歷
* @param root 樹的根結點
*/
public void postOrder(Tree root) {
if(!root.isEmpty()) {
for (Tree child : root.getChilds()) {
if(child != null) {
preOrder(child);
}
}
visit(root);
}
}
public void visit(Tree tree) {
System.out.print("\t" + tree.getRootData());
}
}測試：
要遍歷的樹如下：
package datastructure.tree;
import java.util.Iterator;
import java.util.Scanner;
public class TreeTest {
/**
* @param args
*/
public static void main(String[] args) {
Tree root = new Tree("A");
root.addNode(new Tree("B"));
root.addNode(new Tree("C"));
root.addNode(new Tree("D"));
Tree t = null;
t = root.getChild(0);
t.addNode(new Tree("L"));
t.addNode(new Tree("E"));
t = root.getChild(1);
t.addNode(new Tree("F"));
t = root.getChild(2);
t.addNode(new Tree("I"));
t.addNode(new Tree("H"));
t = t.getFirstChild();
t.addNode(new Tree("L"));
System.out.println("first node:" + root.getRootData());
//System.out.println("size:" + root.size());
//System.out.println("dept:" + root.dept());
System.out.println("is left:" + root.isLeaf());
System.out.println("data:" + root.getRootData());
Order order = new Order();
System.out.println("前根遍歷：");
order.preOrder(root);
System.out.println("\n后根遍歷：");
order.postOrder(root);
}
}結果：
first node:A
is left:false
data:A
前根遍歷：
A BL E C F DI L H
后根遍歷：
B LE C F D IL H A
以上是“java數(shù)據(jù)結構之樹的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！
文章名稱：java數(shù)據(jù)結構之樹的示例分析
URL分享：http://jinyejixie.com/article12/gpesdc.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、網(wǎng)站排名、軟件開發(fā)、ChatGPT、網(wǎng)站設計公司、移動網(wǎng)站建設
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 營銷型網(wǎng)站建設動態(tài)頁面和靜態(tài)頁面區(qū)別 2016-10-26
- 你需要知道的提升網(wǎng)站排名的SEO技術 2013-04-25
- 網(wǎng)站排名點擊軟件需要注意什么？ 2013-12-28
- 企業(yè)常用的SEO關鍵詞優(yōu)化技巧有哪些? 2016-11-08
- 網(wǎng)站改版需要注意的六大SEO優(yōu)化細節(jié) 2016-10-29
- 如何通過優(yōu)化使網(wǎng)站排名在首頁 2013-04-29
- 如何有效的做SEO搜索引擎優(yōu)化 2014-07-14
- 文章更新后很快就收錄并有排名然后收錄又被刪除是怎么回事？ 2016-11-04
- 如何利用QQ來進行企業(yè)網(wǎng)站營銷？ 2016-12-22
- 【網(wǎng)站排名優(yōu)化】網(wǎng)站優(yōu)化必須要做的幾個事情 2016-11-12
- 網(wǎng)站優(yōu)化不被收錄有哪些原因? 2013-12-05
- 一起來看看站長必看的網(wǎng)站快速收錄方法 2013-07-23