Javaツリーの格納構造の実装例コード
一、木
ツリーは線形表、スタック、キューなどの線形構造とは異なり、ツリーは非線形構造である。
一本の木には一本のノードしかない。一本の木に複数のノードがあると、もう一本の木ではなく、複数の木の集合であり、森林とも呼ばれる。
二、木の親ノード表示法
ツリー内のルートノードを除いた各ノードには親ノードがあり、ツリー内のノードとノードとの間の親子関係を記録するために、各ノードのためにparentドメインを追加して、ノードの親ノードを記録することができる。
TreePart$Node[data=root，parent=-1]
この木の深さ:2
ルートノードの第1のサブノード：TreePart$Node[data=ノード1,parent=0]
この木の深さ:3
三、サブノードチェーン表示法
親ノードにすべてのサブノードを記憶させる。
TreeChild$Node[data=root，first=-1]
サブノードを追加した後のルートノード：TreeChildドルNode[data=root，first=1]
この木の深さ:2
ルートノードの第1のサブノード：TreeChildドルNode[data=ノード1,first=-1]
このツリーの第一サブノード：TreeChild$Node[data=ノード1,first=4]
この木の深さ:3
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。
ツリーは線形表、スタック、キューなどの線形構造とは異なり、ツリーは非線形構造である。
一本の木には一本のノードしかない。一本の木に複数のノードがあると、もう一本の木ではなく、複数の木の集合であり、森林とも呼ばれる。
二、木の親ノード表示法
ツリー内のルートノードを除いた各ノードには親ノードがあり、ツリー内のノードとノードとの間の親子関係を記録するために、各ノードのためにparentドメインを追加して、ノードの親ノードを記録することができる。
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;
//
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[]
private Node<E>[] nodes;
//
private int nodeNums;
//
public TreeParent(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data, -1);
nodeNums++;
}
// 、 treeSize
public TreeParent(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data, -1);
nodeNums++;
}
//
public void addNode(E data, Node parent) {
for (int i = 0; i < treeSize; i++) {
// null ，
if (nodes[i] == null) {
// ，
nodes[i] = new Node(data, pos(parent));
nodeNums++;
return;
}
}
throw new RuntimeException(" ， ");
}
//
public boolean empty() {
// null
return nodes[0] == null;
}
//
public Node<E> root() {
//
return nodes[0];
}
// （ ）
public Node<E> parent(Node node) {
// parent
return nodes[node.parent];
}
// （ ）
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<Node<E>>();
for (int i = 0; i < treeSize; i++) {
// parent
if (nodes[i] != null && nodes[i].parent == pos(parent)) {
list.add(nodes[i]);
}
}
return list;
}
//
public int deep() {
//
int max = 0;
for (int i = 0; i < treeSize && nodes[i] != null; i++) {
//
int def = 1;
// m
int m = nodes[i].parent;
//
while (m != -1 && nodes[m] != null) {
//
m = nodes[m].parent;
def++;
}
if (max < def) {
max = def;
}
}
return max;
}
//
public int pos(Node node) {
for (int i = 0; i < treeSize; i++) {
//
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(" 1", root);
System.out.println(" ：" + tp.deep());
tp.addNode(" 2", root);
//
List<TreeParent.Node<String>> nodes = tp.children(root);
System.out.println(" ：" + nodes.get(0));
//
tp.addNode(" 3", nodes.get(0));
System.out.println(" ：" + tp.deep());
}
}
TreePart$Node[data=root，parent=-1]
この木の深さ:2
ルートノードの第1のサブノード：TreePart$Node[data=ノード1,parent=0]
この木の深さ:3
三、サブノードチェーン表示法
親ノードにすべてのサブノードを記憶させる。
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 {
//
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;
//
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[]
private Node<E>[] nodes;
//
private int nodeNums;
//
public TreeChild(E data) {
treeSize = DEFAULT_TREE_SIZE;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data);
nodeNums++;
}
// 、 treeSize
public TreeChild(E data, int treeSize) {
this.treeSize = treeSize;
nodes = new Node[treeSize];
nodes[0] = new Node<E>(data);
nodeNums++;
}
//
public void addNode(E data, Node parent) {
for (int i = 0; i < treeSize; i++) {
// null ，
if (nodes[i] == null) {
// ，
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(" ， ");
}
//
public boolean empty() {
// null
return nodes[0] == null;
}
//
public Node<E> root() {
//
return nodes[0];
}
// （ ）
public List<Node<E>> children(Node parent) {
List<Node<E>> list = new ArrayList<Node<E>>();
// parent
SonNode next = parent.first;
//
while (next != null) {
//
list.add(nodes[next.pos]);
next = next.next;
}
return list;
}
// （ ） index
public Node<E> child(Node parent, int index) {
// parent
SonNode next = parent.first;
//
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;
//
while (next != null) {
//
int tmp = deep(nodes[next.pos]);
if (tmp > max) {
max = tmp;
}
next = next.next;
}
// ， + 1
return max + 1;
}
}
//
public int pos(Node node) {
for (int i = 0; i < treeSize; i++) {
//
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(" 1", root);
tp.addNode(" 2", root);
tp.addNode(" 3", root);
System.out.println(" ：" + root);
System.out.println(" ：" + tp.deep());
//
List<TreeChild.Node<String>> nodes = tp.children(root);
System.out.println(" ：" + nodes.get(0));
//
tp.addNode(" 4", nodes.get(0));
System.out.println(" ：" + nodes.get(0));
System.out.println(" ：" + tp.deep());
}
}
TreeChild$Node[data=root，first=-1]
サブノードを追加した後のルートノード：TreeChildドルNode[data=root，first=1]
この木の深さ:2
ルートノードの第1のサブノード：TreeChildドルNode[data=ノード1,first=-1]
このツリーの第一サブノード：TreeChild$Node[data=ノード1,first=4]
この木の深さ:3
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。