Java中樹的存儲結(jié)構(gòu)實現(xiàn)示例代碼
更新時間：2017年09月21日 10:12:42 作者：遠(yuǎn)進
本篇文章主要介紹了Java中樹的存儲結(jié)構(gòu)實現(xiàn)示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
一、樹
樹與線性表、棧、隊列等線性結(jié)構(gòu)不同，樹是一種非線性結(jié)構(gòu)。
一棵樹只有一個根節(jié)點，如果一棵樹有了多個根節(jié)點，那它已經(jīng)不再是一棵樹了，而是多棵樹的集合，也被稱為森林。
二、樹的父節(jié)點表示法
樹中除根節(jié)點之外每個節(jié)點都有一個父節(jié)點，為了記錄樹中節(jié)點與節(jié)點之間的父子關(guān)系，可以為每個節(jié)點增加一個parent域，用以記錄該節(jié)點的父節(jié)點。
package com.ietree.basic.datastructure.tree;
import java.util.ArrayList;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class TreeParent<E> {
public static class Node<T> {
T data;
// 保存其父節(jié)點的位置
int parent;
public Node() {
}
public Node(T data) {
this.data = data;
}
public Node(T data, int parent) {
this.data = data;
this.parent = parent;
}
public String toString() {
return "TreeParent$Node[data=" + data + ", parent=" + parent + "]";
}
}
private final int DEFAULT_TREE_SIZE = 100;
private int treeSize = 0;
// 使用一個Node[]數(shù)組來記錄該樹里的所有節(jié)點
private Node<E>[] nodes;
// 記錄樹的節(jié)點數(shù)
private int nodeNums;
// 以指定節(jié)點創(chuàng)建樹
public TreeParent(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data, -1);
nodeNums++;
}
// 以指定根節(jié)點、指定treeSize創(chuàng)建樹
public TreeParent(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data, -1);
nodeNums++;
}
// 為指定節(jié)點添加子節(jié)點
public void addNode(E data, Node parent) {
for (int i = 0; i < treeSize; i++) {
// 找到數(shù)組中第一個為null的元素，該元素保存新節(jié)點
if (nodes[i] == null) {
// 創(chuàng)建新節(jié)點，并用指定的數(shù)組元素保存它
nodes[i] = new Node(data, pos(parent));
nodeNums++;
return;
}
}
throw new RuntimeException("該樹已滿，無法添加新節(jié)點");
}
// 判斷樹是否為空
public boolean empty() {
// 根結(jié)點是否為null
return nodes[0] == null;
}
// 返回根節(jié)點
public Node<E> root() {
// 返回根節(jié)點
return nodes[0];
}
// 返回指定節(jié)點（非根結(jié)點）的父節(jié)點
public Node<E> parent(Node node) {
// 每個節(jié)點的parent記錄了其父節(jié)點的位置
return nodes[node.parent];
}
// 返回指定節(jié)點（非葉子節(jié)點）的所有子節(jié)點
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<Node<E>>();
for (int i = 0; i < treeSize; i++) {
// 如果當(dāng)前節(jié)點的父節(jié)點的位置等于parent節(jié)點的位置
if (nodes[i] != null && nodes[i].parent == pos(parent)) {
list.add(nodes[i]);
}
}
return list;
}
// 返回該樹的深度
public int deep() {
// 用于記錄節(jié)點的最大深度
int max = 0;
for (int i = 0; i < treeSize && nodes[i] != null; i++) {
// 初始化本節(jié)點的深度
int def = 1;
// m 記錄當(dāng)前節(jié)點的父節(jié)點的位置
int m = nodes[i].parent;
// 如果其父節(jié)點存在
while (m != -1 && nodes[m] != null) {
// 向上繼續(xù)搜索父節(jié)點
m = nodes[m].parent;
def++;
}
if (max < def) {
max = def;
}
}
return max;
}
// 返回包含指定值的節(jié)點
public int pos(Node node) {
for (int i = 0; i < treeSize; i++) {
// 找到指定節(jié)點
if (nodes[i] == node) {
return i;
}
}
return -1;
}
}
測試類：
package com.ietree.basic.datastructure.tree;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class treeParentTest {
public static void main(String[] args) {
TreeParent<String> tp = new TreeParent<String>("root");
TreeParent.Node root = tp.root();
System.out.println(root);
tp.addNode("節(jié)點1", root);
System.out.println("此樹的深度：" + tp.deep());
tp.addNode("節(jié)點2", root);
// 獲取根節(jié)點的所有子節(jié)點
List<TreeParent.Node<String>> nodes = tp.children(root);
System.out.println("根節(jié)點的第一個子節(jié)點：" + nodes.get(0));
// 為根節(jié)點的第一個子節(jié)點新增一個子節(jié)點
tp.addNode("節(jié)點3", nodes.get(0));
System.out.println("此樹的深度：" + tp.deep());
}
}
程序輸出：
TreeParent$Node[data=root, parent=-1]
此樹的深度：2
根節(jié)點的第一個子節(jié)點：TreeParent$Node[data=節(jié)點1, parent=0]
此樹的深度：3
三、子節(jié)點鏈表示法
讓父節(jié)點記住它的所有子節(jié)點。
package com.ietree.basic.datastructure.tree;
import java.util.ArrayList;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class TreeChild<E> {
private static class SonNode {
// 記錄當(dāng)前節(jié)點的位置
private int pos;
private SonNode next;
public SonNode(int pos, SonNode next) {
this.pos = pos;
this.next = next;
}
}
public static class Node<T> {
T data;
// 記錄第一個子節(jié)點
SonNode first;
public Node(T data) {
this.data = data;
this.first = null;
}
public String toString() {
if (first != null) {
return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]";
} else {
return "TreeChild$Node[data=" + data + ", first=-1]";
}
}
}
private final int DEFAULT_TREE_SIZE = 100;
private int treeSize = 0;
// 使用一個Node[]數(shù)組來記錄該樹里的所有節(jié)點
private Node<E>[] nodes;
// 記錄節(jié)點數(shù)
private int nodeNums;
// 以指定根節(jié)點創(chuàng)建樹
public TreeChild(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data);
nodeNums++;
}
// 以指定根節(jié)點、指定treeSize創(chuàng)建樹
public TreeChild(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data);
nodeNums++;
}
// 為指定節(jié)點添加子節(jié)點
public void addNode(E data, Node parent) {
for (int i = 0; i < treeSize; i++) {
// 找到數(shù)組中第一個為null的元素，該元素保存新節(jié)點
if (nodes[i] == null) {
// 創(chuàng)建新節(jié)點，并用指定數(shù)組元素保存它
nodes[i] = new Node(data);
if (parent.first == null) {
parent.first = new SonNode(i, null);
} else {
SonNode next = parent.first;
while (next.next != null) {
next = next.next;
}
next.next = new SonNode(i, null);
}
nodeNums++;
return;
}
}
throw new RuntimeException("該樹已滿，無法添加新節(jié)點");
}
// 判斷樹是否為空
public boolean empty() {
// 根結(jié)點是否為null
return nodes[0] == null;
}
// 返回根節(jié)點
public Node<E> root() {
// 返回根節(jié)點
return nodes[0];
}
// 返回指定節(jié)點（非葉子節(jié)點）的所有子節(jié)點
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<Node<E>>();
// 獲取parent節(jié)點的第一個子節(jié)點
SonNode next = parent.first;
// 沿著孩子鏈不斷搜索下一個孩子節(jié)點
while (next != null) {
// 添加孩子鏈中的節(jié)點
list.add(nodes[next.pos]);
next = next.next;
}
return list;
}
// 返回指定節(jié)點（非葉子節(jié)點）的第index個子節(jié)點
public Node<E> child(Node parent, int index) {
// 獲取parent節(jié)點的第一個子節(jié)點
SonNode next = parent.first;
// 沿著孩子鏈不斷搜索下一個孩子節(jié)點
for (int i = 0; next != null; i++) {
if (index == i) {
return nodes[next.pos];
}
next = next.next;
}
return null;
}
// 返回該樹的深度
public int deep() {
// 獲取該樹的深度
return deep(root());
}
// 這是一個遞歸方法：每棵子樹的深度為其所有子樹的最大深度 + 1
private int deep(Node node) {
if (node.first == null) {
return 1;
} else {
// 記錄其所有子樹的最大深度
int max = 0;
SonNode next = node.first;
// 沿著孩子鏈不斷搜索下一個孩子節(jié)點
while (next != null) {
// 獲取以其子節(jié)點為根的子樹的深度
int tmp = deep(nodes[next.pos]);
if (tmp > max) {
max = tmp;
}
next = next.next;
}
// 最后，返回其所有子樹的最大深度 + 1
return max + 1;
}
}
// 返回包含指定值得節(jié)點
public int pos(Node node) {
for (int i = 0; i < treeSize; i++) {
// 找到指定節(jié)點
if (nodes[i] == node) {
return i;
}
}
return -1;
}
}
測試類：
package com.ietree.basic.datastructure.tree;
import java.util.List;
/**
* Created by ietree
* 2017/4/30
*/
public class TreeChildTest {
public static void main(String[] args) {
TreeChild<String> tp = new TreeChild<String>("root");
TreeChild.Node root = tp.root();
System.out.println(root);
tp.addNode("節(jié)點1", root);
tp.addNode("節(jié)點2", root);
tp.addNode("節(jié)點3", root);
System.out.println("添加子節(jié)點后的根結(jié)點：" + root);
System.out.println("此樹的深度：" + tp.deep());
// 獲取根節(jié)點的所有子節(jié)點
List<TreeChild.Node<String>> nodes = tp.children(root);
System.out.println("根節(jié)點的第一個子節(jié)點：" + nodes.get(0));
// 為根節(jié)點的第一個子節(jié)點新增一個子節(jié)點
tp.addNode("節(jié)點4", nodes.get(0));
System.out.println("此樹第一個子節(jié)點：" + nodes.get(0));
System.out.println("此樹的深度：" + tp.deep());
}
}
程序輸出：
TreeChild$Node[data=root, first=-1]
添加子節(jié)點后的根結(jié)點：TreeChild$Node[data=root, first=1]
此樹的深度：2
根節(jié)點的第一個子節(jié)點：TreeChild$Node[data=節(jié)點1, first=-1]
此樹第一個子節(jié)點：TreeChild$Node[data=節(jié)點1, first=4]
此樹的深度：3
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
深度剖析Java成員變量、局部變量和靜態(tài)變量的創(chuàng)建和回收時機
這篇文章主要介紹了深度剖析Java成員變量、局部變量和靜態(tài)變量的創(chuàng)建和回收時機,成員變量是定義在類中的變量，每個類的實例都會擁有自己的成員變量。它們的生命周期與對象的創(chuàng)建和銷毀相對應(yīng),下面我將詳細(xì)介紹它們的特點和生命周期,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了什么是BIO以及如何使用,BIO英文全名是blockingIO,也叫做阻塞IO,是最容易理解、最容易實現(xiàn)的IO工作方式,本文就來通過一些簡單的示例為大家講講BIO吧,需要的朋友可以參考下2023-10-10
spring自定義注解實現(xiàn)攔截器的實現(xiàn)方法
本篇文章主要介紹了spring自定義注解實現(xiàn)攔截器的實現(xiàn)方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
這篇文章主要為大家介紹了Spring管理Controller可行性原理示例分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
解決spring mvc 多數(shù)據(jù)源切換,不支持事務(wù)控制的問題
下面小編就為大家?guī)硪黄鉀Qspring mvc 多數(shù)據(jù)源切換,不支持事務(wù)控制的問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
這篇文章主要介紹了SpringBoot靜態(tài)資源及原理解析,當(dāng)創(chuàng)建一個jar工程時,想引入css等靜態(tài)資源時,需要遵守SpringBoot的靜態(tài)資源映射關(guān)系,通過WebMvcAutoConfiguration查看靜態(tài)配置資源的規(guī)則,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了Spring Boot 配置隨機數(shù)技巧，spring boot 支持在系統(tǒng)加載的時候配置隨機數(shù)，具體實例代碼大家參考下本文2018-05-05
Jedis是Redis官方推薦的用于訪問Java客戶端，下面這篇文章主要給大家介紹了關(guān)于Java客戶端利用Jedis操作redis緩存的相關(guān)資料，文中給出了詳細(xì)的示例代碼，需要的朋友可以參考借鑒，下面來一起看看吧。2017-07-07
這篇文章主要介紹了spring boot發(fā)簡單文本郵件案例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-10-10
在JavaMaven項目中引入自己的庫可以簡化為幾個步驟：首先,確保庫以JAR格式存在或打包成JAR；其次,將JAR文件放置在項目目錄或安裝到本地Maven倉庫；最后,在pom.xml中添加依賴,這樣做可以使項目更加模塊化,便于管理和維護,感興趣的朋友跟隨小編一起看看吧2024-09-09