一、树

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

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

二、树的父节点表示法

树中除根节点之外每个节点都有一个父节点，为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。