树的定义
树(Tree)是n(n≥0)个结点的有限集T，并且当n＞0时满足下列条件：
1.有且仅有一个特定的称为根(Root)的结点；
2.当n＞1时，其余结点可以划分为m(m＞0)个互不相交的有限集T1、T2 、…、Tm，每个集Ti(1≤i≤m)均为树，且称为树T的子树(SubTree)。
不含任何结点(即n＝0)的树，称为空树。
如下图就是一棵树的结构：
树的基本术语
结点：存储数据元素和指向子树的链接，由数据元素和构造数据元素之间关系的引用组成。
孩子结点：树中一个结点的子树的根结点称为这个结点的孩子结点，如上图中的A的孩子结点有B、C、D
双亲结点：树中某个结点有孩子结点(即该结点的度不为0)，该结点称为它孩子结点的双亲结点，也叫前驱结点。双亲结点和孩子结点是相互的，如上图中，A的孩子结点是B、C、D，B、C、D的双亲结点是A。
兄弟结点：具有相同双亲结点(即同一个前驱)的结点称为兄弟结点，如上图中B、B、D为兄弟结点。
结点的度：结点所有子树的个数称为该结点的度，如上图，A的度为3，B的度为2.
树的度：树中所有结点的度的最大值称为树的度，如上图的度为3.
叶子结点：度为0的结点称为叶子结点，也叫终端结点。如上图的K、L、F、G、M、I、J
分支结点：度不为0的结点称为分支结点，也叫非终端结点。如上图的A、B、C、D、E、H
结点的层次：从根结点到树中某结点所经路径的分支数称为该结点的层次。根结点的层次一般为1(也可以自己定义为0)，这样，其它结点的层次是其双亲结点的层次加1.
树的深度：树中所有结点的层次的最大值称为该树的深度(也就是最下面那个结点的层次)。
有序树和无序树：树中任意一个结点的各子树按从左到右是有序的，称为有序树，否则称为无序树。
树的抽象数据类型描述
ADT 树（Tree）
Data
具有相同特性的数据元素的集合；树中数据元素间的结构关系由树的定义确定。
Operation
（1）initTree(T）：创建1个空树T
（2）destroyTree(T)：销毁树
（3）creatTree(T，deinition):构造树
（4）clearTree(T):置空树,将树T置为空树
（5）treeEmpty(T):判空树
（6）treeDepth(T):求树的深度
（7）root(T):获得树根
（8）value(T，cur_e，e):获取结点,将树中结点cur_e存入e单元中。
（9）assign(T，cur_e，value):数据赋值,将结点value，赋值于树T的结点cur_e中。
（10）parent(T，cur_e):获得双亲, 返回树T中结点cur_e的双亲结点。
（11）leftChild(T，cur_e):获得最左孩子,返回树T中结点cur_e的最左孩子。
（12）rightSibling(T，cur_e):获得右兄弟,返回树T中结点cur_e的右兄弟。
（13）InsertChild(T，p，i，c):插入子树,将树c插入到树T中p指向结点的第i个子树之前。
（14）deleteChild(T，p，i):删除子树, 删除树T中p指向结点的第i个子树。
（15）traverseTree(T，visit()):遍历树
endADT
树的实现
树是一种递归结构，表示方式一般有孩子兄弟表示法和孩子表示法两种。树实现方式有很多种、有可以由广义表的递归实现，也可以有二叉树实现，其中最常见的是将树用孩子兄弟表示法转化成二叉树来实现,如下图：
/**
* 以孩子表示法为例讲一下树的实现
* @author wangxiaojian
*/
public class Tree {
private Object data;
private List<Tree> childs;
public Tree() {
data = null;
childs = new ArrayList<>();
}
public Tree(Object data) {
this.data = data;
childs = new ArrayList<>();
}
/**
* 添加子树
*
* @param tree 子树
*/
public void addNode(Tree tree) {
childs.add(tree);
}
/**
* 置空树
*/
public void clearTree() {
data = null;
childs.clear();
}
/**
* 求树的深度
*
* @return 树的深度
*/
public int dept() {
return dept(this);
}
/**
* 求树的深度
*
* @param tree
* @return
*/
private int dept(Tree tree) {
if (tree.isEmpty()) {
return 0;
} else if (tree.isLeaf()) {
return 1;
} else {
int n = childs.size();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
if (childs.get(i).isEmpty()) {
a[i] = 0 + 1;
} else {
a[i] = dept(childs.get(i)) + 1;
}
}
Arrays.sort(a);
return a[n - 1];
}
}
/**
* 返回递i个子树
*
* @param i
* @return
*/
public Tree getChild(int i) {
return childs.get(i);
}
/**
* 求第一个孩子 结点
*
* @return
*/
public Tree getFirstChild() {
return childs.get(0);
}
/**
* 求最后 一个孩子结点
*
* @return
*/
public Tree getLastChild() {
return childs.get(childs.size() - 1);
}
public List<Tree> getChilds() {
return childs;
}
/**
* 获得根结点的数据
*
* @return
*/
public Object getRootData() {
return data;
}
/**
* 判断是否为空树
*
* @return 如果为空，返回true,否则返回false
*/
public boolean isEmpty() {
if (childs.isEmpty() && data == null) {
return true;
}
return false;
}
/**
* 判断是否为叶子结点
*
* @return
*/
public boolean isLeaf() {
if (childs.isEmpty()) {
return true;
}
return false;
}
/**
* 获得树根
*
* @return 树的根
*/
public Tree root() {
return this;
}
/**
* 设置根结点的数据
*/
public void setRootData(Object data) {
this.data = data;
}
/**
* 求结点数
*
* @return 结点的个数
*/
public int size() {
return size(this);
}
/**
* 求结点数
*
* @param tree
* @return
*/
private int size(Tree tree) {
if (tree.isEmpty()) {
return 0;
} else if (tree.isLeaf()) {
return 1;
} else {
int count = 1;
int n = childs.size();
for(int i=0; i<n; i++) {
if(!childs.get(i).isEmpty()) {
count += size(childs.get(i));
}
}
return count;
}
}
}
网友评论