树：
定义：
树是n个节点的有限集。n=0时称为空树。在任意一颗非空树中：（1）有且仅有一个特定的称为根（Root）的结点，（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3、……Tm，其中每一个集合本身又是一颗树，并称为根的子树，如下图
概念：
- 树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf） 或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。因为这棵树结点的度的最大值是结点D的度为3，所以树的度也为3，如下图：
- 结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟，如下图：
- 结点的层次从根开始，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟，树中结点的最大层次称为树的深度或者高度，如下图：
树的父节点表示法：
import java.util.ArrayList;
import java.util.List;
/**
* 树的父节点表示法
* @author wydream
*
*/
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<E> parent) {
for(int i=0;i<treeSize;i++) {
// 找到数组中第一个为null的元素，该元素保存新节点
if(nodes[i]==null) {
nodes[i]=new Node<E>(data,pos(parent));
nodeNums++;
return;
}
// 创建新节点，并用指定的数组元素保存它
}
throw new RuntimeException("该树已满");
}
// 判断树是否为空
public boolean isEmpty() {
return nodes[0]==null;
}
// 返回根节点
public Node<E> root() {
return nodes[0];
}
// 返回指定节点（非根结点）的父节点
public Node<E> parent(Node<E> node) {
return nodes[node.parent];
}
// 返回指定节点（非叶子节点）的所有子节点
public List<Node<E>> children(Node<E> 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<E> node) {
for(int i=0;i<treeSize;i++) {
//找到指定节点
if(nodes[i]==node) {
return i;
}
}
return -1;
}
//测试
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
树的子节点表示法：
import java.util.ArrayList;
import java.util.List;
/**
* 树的子节点表示法
* @author wydream
*
*/
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 isEmpty() {
return nodes[0]==null;
}
//返回根节点
public Node<E> root(){
return nodes[0];
}
//返回指定节点的所有子节点
public List<Node<E>> children(Node<E> 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
public 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;
}
//测试
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