-
树相关的概念
tree01.png
根节点：没有父节点的节点(图中A、1)
叶子节点：没有子节点的节点(图中B、D、3、5)
普通节点：有子节点的节点(图中C、2、4)
节点的度(degree)：节点拥有的子树的个数称为该节点的度(例如，C节点的度为2，2节点的度为3)
树的度：树中所有节点的度的最大值(例如，左边的树的度为3)
节点的层次(level)：节点的层次从根开始算起，根的层次为1，其余节点的层次值为其父节点的层次值加1
数的深度(depth)：树中节点的最大层次值称为树的深度(例如，左边的树的深度为3，右边的树的深度为4)
森林：两颗或两颗以上互不相交的树的集合 -
用代码实现表示一棵树的方法
tree02.png
范例树
(1) 父节点表示法
| 数组索引 | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 1 |
| 5 | F | 3 |
| 6 | G | 3 |
| 7 | H | 4 |
| 8 | I | 4 |
| 9 | J | 4 |
| 10 | K | 6 |
以下程序采用父节点表示法实现了一棵树：
import java.util.ArrayList;
import java.util.List;
/**
* @Description: 使用父节点表示法实现一棵树
* @author Jed
* @date 2018年1月31日
* @param <E>
*/
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;
}
@Override
public String toString() {
return "TreeParent$Node [data=" + data + ", parent=" + parent + "]";
}
}
private final int DEFAULT_TREE_SIZE = 100; // 默认的树的大小
private int treeSize = 0;
private Node<E>[] nodes; // 使用一个Node[]数组来记录该树中的所有节点
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 int getNodeIndex(Node node) {
for(int i = 0; i < treeSize; i++) {
// 找到指定节点
if(nodes[i] == node) {
return i;
}
}
return -1;
}
/**
* 为指定节点添加子节点
*/
public void addNode(E data, Node parent) {
for(int i = 0; i < treeSize; i++) {
if(nodes[i] == null) {
// 创建新节点，并用指定的数组元素保存它
nodes[i] = new Node(data, getNodeIndex(parent));
nodeNums++;
return;
}
}
throw new RuntimeException("该树已满，无法添加新节点");
}
/**
* 判断树是否为空
*/
public boolean isEmpty() {
return nodes[0] == null;
}
/**
* 返回根节点
*/
public Node<E> getRoot() {
return nodes[0];
}
/**
* 返回指定节点(非根节点)的父节点
*/
public Node<E> getParent(Node node) {
// 每个节点的parent记录了其父节点的索引
return nodes[node.parent];
}
public Node<E> getNodeByData(E data) {
for(int i = 0; i < treeSize; i++) {
if(nodes[i].data == data) {
return nodes[i];
}
}
System.out.println("树中不存在包含该数据的节点");
return null;
}
/**
* 返回指定节点(非叶子节点)的所有子节点
*/
public List<Node<E>> getChildren(Node parent) {
List<Node<E>> list = new ArrayList<>();
for(int i = 0; i < treeSize; i++) {
if(nodes[i] != null && nodes[i].parent == getNodeIndex(parent)) {
list.add(nodes[i]);
}
}
return list;
}
/**
* 返回树的深度
*/
public int getDeep() {
int max = 0; // 用于记录节点的最大层次值
for(int i = 0; i < treeSize && nodes[i] != null; i++) {
int def = 1; // 初始化本节点的深度
int m = nodes[i].parent; // 当前节点的父节点的索引
// 如果其父节点存在
while(m != -1 && nodes[m] != null) {
// 继续向上搜索父节点
m = nodes[m].parent;
def ++;
}
if(max < def) {
max = def;
}
}
return max;
}
}
import java.util.List;
public class TreeParentTest {
public static void main(String[] args) {
TreeParent<String> tree = new TreeParent<String>("root");
TreeParent.Node<String> root = tree.getRoot();
System.out.println(root);
tree.addNode("A", root);
tree.addNode("B", root);
TreeParent.Node<String> A = tree.getNodeByData("A");
TreeParent.Node<String> B = tree.getNodeByData("B");
tree.addNode("C", A);
tree.addNode("D", A);
tree.addNode("E", B);
tree.addNode("F", B);
System.out.println("树的深度为：" + tree.getDeep());
List<TreeParent.Node<String>> list = tree.getChildren(A);
System.out.println("A节点的子节点为：");
for(TreeParent.Node<String> node : list) {
System.out.println(node);
}
}
}
结果：
TreeParent$Node [data=root, parent=-1]
树的深度为：3
A节点的子节点为：
TreeParent$Node [data=C, parent=1]
TreeParent$Node [data=D, parent=1]
父节点表示法的特点：
每个节点可以快速找到父节点
找某个节点的子节点需要遍历整颗树
(2) 子节点链表示法
| 数组索引 | data | child |
|---|---|---|
| 0 | A | 1 -> 2 -> 3 |
| 1 | B | 4 |
| 2 | C | |
| 3 | D | 5 -> 6 |
| 4 | E | 7 -> 8 -> 9 |
| 5 | F | |
| 6 | G | 10 |
| 7 | H | |
| 8 | I | |
| 9 | J | |
| 10 | K |
以下程序采用子节点链表示法实现了一棵树：
import java.util.ArrayList;
import java.util.List;
/**
* @Description: 使用子节点链表示法实现一棵树
* @author Jed
* @date 2018年1月31日
*/
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;
}
@Override
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;
private Node<E>[] nodes; // 使用一个Node[]数组来记录该树中的所有节点
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 int getNodeIndex(Node node) {
for(int i = 0; i < treeSize; i++) {
// 找到指定节点
if(nodes[i] == node) {
return i;
}
}
return -1;
}
/**
* 为指定节点添加子节点
*/
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 isEmpty() {
return nodes[0] == null;
}
/**
* 返回根节点
*/
public Node<E> getRoot() {
return nodes[0];
}
/**
* 返回指定节点(非叶子节点)的所有子节点
*/
public List<Node<E>> getChildren(Node parent) {
List<Node<E>> list = new ArrayList<>();
// 获取parent节点的第一个子节点
SonNode next = parent.first;
// 沿着孩子链不断搜索下一个孩子节点
while(next != null) {
// 添加孩子链中的节点
list.add(nodes[next.pos]);
next = next.next;
}
return list;
}
/**
* 返回指定节点(非叶子节点)的第index个子节点
*/
public Node<E> getChild(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;
}
// 这是一个递归方法，每颗子树的深度为其所有子树的深度 +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;
}
return max + 1;
}
}
/**
* 返回该树的深度
*/
public int getDeep() {
return deep(getRoot());
}
}
import java.util.List;
public class TreeChildTest {
public static void main(String[] args) {
TreeChild<String> tc = new TreeChild<String>("root");
TreeChild.Node<String> root = tc.getRoot();
System.out.println(root);
tc.addNode("A", root);
tc.addNode("B", root);
TreeChild.Node<String> A = tc.getChild(root, 0);
TreeChild.Node<String> B = tc.getChild(root, 1);
tc.addNode("C", A);
tc.addNode("D", A);
tc.addNode("E", B);
tc.addNode("F", B);
System.out.println("树的深度为：" + tc.getDeep());
List<TreeChild.Node<String>> list = tc.getChildren(A);
System.out.println("A节点的子节点为：");
for(TreeChild.Node<String> node : list) {
System.out.println(node);
}
System.out.println(A);
System.out.println(B);
}
}
结果：
TreeChild$Node [data=root, first=-1]
树的深度为：3
A节点的子节点为：
TreeChild$Node [data=C, first=-1]
TreeChild$Node [data=D, first=-1]
TreeChild$Node [data=A, first=3]
TreeChild$Node [data=B, first=5]
子节点链表示法的特点：
每个节点都可以快速找到它的所有子节点
但要找到某个节点的父节点则需要遍历整颗树
网友评论