Java中樹的存儲結構實現(xiàn)示例代碼
更新時間：2017年09月21日 10:12:42 作者：遠進
本篇文章主要介紹了Java中樹的存儲結構實現(xiàn)示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
一、樹
樹與線性表、棧、隊列等線性結構不同，樹是一種非線性結構。
一棵樹只有一個根節(jié)點，如果一棵樹有了多個根節(jié)點，那它已經(jīng)不再是一棵樹了，而是多棵樹的集合，也被稱為森林。
二、樹的父節(jié)點表示法
樹中除根節(jié)點之外每個節(jié)點都有一個父節(jié)點，為了記錄樹中節(jié)點與節(jié)點之間的父子關系，可以為每個節(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() {
// 根結點是否為null
return nodes[0] == null;
}
// 返回根節(jié)點
public Node<E> root() {
// 返回根節(jié)點
return nodes[0];
}
// 返回指定節(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++) {
// 如果當前節(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 記錄當前節(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 {
// 記錄當前節(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() {
// 根結點是否為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é)點后的根結點：" + 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é)點后的根結點：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)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
Java實現(xiàn)Excel導入導出數(shù)據(jù)庫的方法示例
這篇文章主要介紹了Java實現(xiàn)Excel導入導出數(shù)據(jù)庫的方法,結合實例形式分析了java針對Excel的讀寫及數(shù)據(jù)庫操作相關實現(xiàn)技巧,需要的朋友可以參考下2017-08-08
synchronized及JUC顯式locks?使用原理解析
這篇文章主要為大家介紹了synchronized及JUC顯式locks?使用原理解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
Java數(shù)據(jù)結構之優(yōu)先級隊列(PriorityQueue)用法詳解
優(yōu)先級隊列是一種先進先出的數(shù)據(jù)結構，操作的數(shù)據(jù)帶有優(yōu)先級，這種數(shù)據(jù)結構就是優(yōu)先級隊列（PriorityQueue）。本文將詳細講講Java優(yōu)先級隊列的用法，感興趣的可以了解一下2022-07-07
這篇文章主要給大家介紹了關于JAVA正則表達式提取key-value類型字符值的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2022-10-10
本篇文章主要介紹了mybatis學習筆記之mybatis注解配置詳解，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
線上項目涉及大量查詢接口中，存在電話號明文展示不合規(guī)的問題。如果對每個接口返回結果中電話號相關字段修改相關代碼邏輯，則工作量較大花費時間多。因此設計電話號加密注解，減少工作量。2021-06-06
這篇文章主要介紹了java的JIT 工作原理簡單介紹的相關資料,需要的朋友可以參考下2017-03-03
這篇文章主要為大家詳細介紹了Java實現(xiàn)多個文檔合并輸出到一個文檔的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
詳解如何使用IntelliJ IDEA新建一個Servlet項目
這篇文章主要介紹了詳解如何使用IntelliJ IDEA新建一個Servlet項目，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-11-11
Java16 JDK安裝并設置環(huán)境變量的方法步驟
突然想起自己大學剛接觸java的時候,要下載JDK和配置環(huán)境變量,那時候我上網(wǎng)找了很多教學，本文就詳細的介紹一下Java16 JDK安裝并設置環(huán)境變量，感興趣的可以了解一下2021-09-09