树是一种非线性的数据结构,它是由 n (n >= 0)个有限结点组成一个具有层次关系的.
把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的.
注意:树形结构中,子树之间不能有交集,否则就不是树形结构,是图结构了.
下面就是一个平平无奇的树
子树 T1 和子树 T2 是根节点 A 的子树,同时 D,G,H,J 组成的树也是以 B 为根节点的子树,所以说树是递归定义的.
对于树的定义还需要强调两点:
结点的度:一个结点含有子树的个数称为该结点的度; 如上图,A的为 2 ,D的为 3
叶结点或终端结点:度为 0 的结点称为叶结点; 如上图, G, H, I, J, F为叶节点
非终端结点或分支结点:度不为 0 的结点; 如上图, A, B, C, D, E为分支结点
双亲结点或父节点:若一个结点含有子节点,则这个结点称为其子节点的父节点; 如上图,A 为 B 的父节点
孩子结点或子节点:一个结点含有的子树的根节点称为该结点的子节点; 如上图,E 是 C 的孩子结点
兄弟结点:具有相同父节点的结点互称为兄弟结点;如上图,G, H, I互称为兄弟结点
树的度:一棵树中,最大的结点的度称为树的度如上图,树的度为 3
结点的层次:从根开始定义起, 根为第1层,根的子节点为第2层,以此类推
树的高度或深度:树中结点的最大层次如上图,该树的高度为4
堂兄弟结点:双亲在同一层的结点互为堂兄弟如上图, I, J互为堂兄弟结点
结点的祖先:从根到该结点所经分支上的所有节点如上图,A 是所有结点的祖先
子孙:以某结点为根的子树中任一节点都称为该节点的子孙如上图:所有结点都是 A 的子孙
森林:由 m (m > 0) 棵互不相交的树的集合称为森林
以前学单链表的时候就有一个指针,双链表有两个指针,但是树有几个指针就不确定了,因为树没有规定每个结点有多少孩子.
有三种方式来表示
说明了树的度为N,使用顺序表表示
每个结点有多个指针域,其中每个指针指向一棵子树的根节点
#define N 3 //假设树的度为N
struct TreeNode
{
int val;
struct TreeNode* child[N]; //指针数组
};
但是这样的表示也有缺陷,就是需要知道树的度,而且很有可能造成空间的浪费
每个结点中,附设一个指示器指示其双亲结点在数组中的位置
struct TreeNode
{
int val;
int parent;
}
虽然找到该结点的双亲结点时间复杂度为 O ( 1 ) O(1) O(1), 但是要找到该结点的子节点却仍然需要遍历整个树才可以找到,显然这个结构也有缺陷
任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的.因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟.
struct TreeNode
{
int val;
struct TreeNode* firstchild;
struct TreeNode* nextbrother;
}
这样可以说是最优的表示法了
如果我们想要得到某个结点的所有孩子,下面的代码就可以了.
struct TreeNode* Anode;
struct TreeNode* child = Anode->firstchild;
while (child)
{
printf("%d ", child->val);
child = child->nextbrother;
}
这样确实做到了最大节省空间,同时,这也是一个二叉树,它的逻辑结构适合很多操作,是一个很优秀的逻辑结构.
文件系统的目录树结构、网络拓扑，最短路径问题，搜索引擎、思维导图等
