一、树
树与线性表、栈、队列等线性结构不同,树是一种非线性结构。
一棵树只有一个根节点,如果一棵树有了多个根节点,那它已经不再是一棵树了,而是多棵树的集合,也被称为森林。
二、树的父节点表示法
树中除根节点之外每个节点都有一个父节点,为了记录树中节点与节点之间的父子关系,可以为每个节点增加一个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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持亿速云。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。