1.树的基本概念
1.1 概念
下面是一个树的例子,下面以这个树介绍基本概念。
A节点是根节点,A节点和F节点由一条边连接;F节点是A节点的儿子,并且是K,L,M节点的父亲。没有儿子节点的节点叫做树叶(例如B,C,H等),具有相同父亲的节点称为兄弟(例如K,L,M)。
对于n1,n2,...nk的序列,对于任何1<=i<=k,ni都是ni+1的父亲节点,这样的序列称为从n1到nk的路径。路径的长等于这条路径上边的个数。对任意节点ni,它的深度就是从根到ni的唯一的路径的长。对任意节点ni,它的高就是从ni到一片树叶的最长路径的长。例如,上图中E的深度为1,高度为2。如果存在一条从 n1到n2的路径,那么n1称为n2的祖先,n2称为n1的后裔,如果n1不等于n2,称为真祖先和真后裔。
1.2 实现:
由于树的每个节点的儿子节点的个数不定,所以实现树时,将树的每个节点的所有儿子都放在树节点的链表中。
class TreeNode{
Object element;
TreeNode firstChild;
TreeNode nextSibling
}
firstChild指向节点的第一个儿子节点,nextSibling指向节点的下一个兄弟节点。
树的一个广泛应用是Unix文件目录模拟。树的遍历一般有2种主要方式,先序遍历是先处理数节点,再处理该节点的孩子节点。后续遍历是先处理该节点的孩子节点,再处理该节点。
2. 二叉树
二叉树是一种树,每个节点的孩子节点不能超过二个。因为二叉树的每个节点至多只有2个孩子节点,所以可以使用下边的数据结构来表示。
class TreeNode {
Object element;
TreeNode left;
TreeNode right;
}
网友评论