Java中树的存储结构实现示例代码

Java中树的存储结构实现示例代码

一、树

树与线性表、栈、队列等线性结构不同，树是一种非线性结构。

一棵树只有一个根节点，如果一棵树有了多个根节点，那它已经不再是一棵树了，而是多棵树的集合，也被称为森林。

二、树的父节点表示法

树中除根节点之外每个节点都有一个父节点，为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个parent域，用以记录该节点的父节点。

package com.ietree.basic.datastructure.tree;

import java.util.ArrayList;

import java.util.List;

/**

* Created by ietree

* 2017/4/30

*/

public class TreeParent {

public static class Node {

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[] nodes;

// 记录树的节点数

private int nodeNums;

// 以指定节点创建树

public TreeParent(E data) {

treeSize = DEFAULT_TREE_SIZE;

nodes = new Node[treeSize];

nodes[0] = new Node(data, -1);

nodeNums++;

}

// 以指定根节点、指定treeSize创建树

public TreeParent(E data, int treeSize) {

this.treeSize = treeSize;

nodes = new Node[treeSize];

nodes[0] = new Node(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 root() {

// 返回根节点

return nodes[0];

}

// 返回指定节点（非根结点）的父节点

public Node parent(Node node) {

// 每个节点的parent记录了其父节点的位置

return nodes[node.parent];

}

// 返回指定节点（非叶子节点）的所有子节点

public List> children(Node parent) {

List> list = new ArrayList>();

for (int i = 0; i < treeSize; i++) {

// 如果当前节点的父节点的位置等于parent节点的位置

if (nodes[i] != null && nodes[i].parent == pos(parenhttp://t)) {

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 tp = new TreeParent("root");

TreeParent.Node root = tp.root();

System.out.println(root);

tp.addNode("节点1", root);

System.out.println("此树的深度：" + tp.deep());

tp.addNode("节点2", root);

// 获取根节点的所有子节点

List> nodes = tp.children(root);

System.out.println("根节点的第一个子节点：" + nodes.get(0));

// 为根节点的第一个子节点新增一个子节点

tp.addNode("节点3", nodes.get(0));

System.out.println("此树的深度：" + tp.deep());

}

}

程序输出：

TreeParent$Node[data=root, parent=-1]

此树的深度：2

根节点的第一个子节点：TreeParent$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 {

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 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[] nodes;

// 记录节点数

private int nodeNums;

// 以指定根节点创建树

public TreeChild(E data) {

Kyctrj treeSize = DEFAULT_TREE_SIZE;

nodes = new Node[treeSize];

nodes[0] = new Node(data);

nodeNums++;

}

// 以指定根节点、指定treeSize创建树

public TreeChild(E data, int treeSize) {

this.treeSize = treeSize;

nodes = new Node[treeSize];

nodes[0] = new Node(data);

nodeNums++;

}

// 为指定节点添加子节点

public void addNode(E data, Node parent) {

for (int i = 0; i < treeSiKyctrjze; 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 root() {

// 返回根节点

return nodes[0];

}

// 返回指定节点（非叶子节点）的所有子节点

public List> children(Node parent) {

List> list = new ArrayList>();

// 获取parent节点的第一个子节点

SonNode next = parent.first;

// 沿着孩子链不断搜索下一个孩子节点

while (next != null) {

// 添加孩子链中的节点

list.add(nodes[next.pos]);

next = next.next;

}

return list;

}

// 返回指定节点（非叶子节点）的第index个子节点

public Node 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 tp = new TreeChild("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> 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

根节点的第一个子节点：TreeChild$Node[data=节点1, first=-1]

此树第一个子节点：TreeChild$Node[data=节点1, first=4]

此树的深度：3

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。