节点的度
一个节点直接含有的子树个数,叫做节点的度。比如上图中的 3 的度是 2,10 的度是 1。
树的度
一棵树中 最大节点的度,即哪个节点的子节点最多,它的度就是 树的度。上图中树的度为 2 。
节点的层次
从根节点开始算起,根节点算第一层,往后底层。比如上图中,3 的层次是 2,4 的层次是 4。
树的高度
树的高度是从叶子节点开始,自底向上增加。
树的深度
与高度相反,树的深度从根节点开始,自顶向下增加。
整个树的高度、深度是一样的,但是中间节点的高度 和 深度是不同的,比如上图中的 6 ,高度是 2 ,深度是 3。
树的两种实现
从上述概念可以得知,树是一个递归的概念,从根节点开始,每个节点至多只有一个父节点,有多个子节点,每个子节点又是一棵树,以此递归。
树有两种实现方式:
数组表示:
我们可以利用每个节点至多只有一个父节点这个特点,使用 父节点表示法 来实现一个节点:
public class TreeNode {
private Object mData; //存储的数据
private int mParent; //父亲节点的下标
public TreeNode(Object data, int parent) {
mData = data;
mParent = parent;
}
public Object getData() {
return mData;
}
public void setData(Object data) {
mData = data;
}
public int getParent() {
return mParent;
}
public void setParent(int parent) {
mParent = parent;
}
}
上述代码中,使用 角标 来指明父亲节点的位置,使用这个节点组成的数组就可以表示一棵树。
public static void main(String[] args){
TreeNode[] arrayTree = new TreeNode[10];
}
用数组实现的树表示下面的树,(其中一种 )结果就是这样的: