Java中树的存储结构实现示例代码
程序员文章站
2024-03-01 23:36:10
一、树
树与线性表、栈、队列等线性结构不同,树是一种非线性结构。
一棵树只有一个根节点,如果一棵树有了多个根节点,那它已经不再是一棵树了,而是多棵树的集合,也被称为森林...
一、树
树与线性表、栈、队列等线性结构不同,树是一种非线性结构。
一棵树只有一个根节点,如果一棵树有了多个根节点,那它已经不再是一棵树了,而是多棵树的集合,也被称为森林。
二、树的父节点表示法
树中除根节点之外每个节点都有一个父节点,为了记录树中节点与节点之间的父子关系,可以为每个节点增加一个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()); } }
程序输出:
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<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
根节点的第一个子节点:treechild$node[data=节点1, first=-1]
此树第一个子节点:treechild$node[data=节点1, first=4]
此树的深度:3
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
上一篇: Hadoop之NameNode Federation图文详解
下一篇: MySQL索引操作命令小结