树(Tree)是一种抽象数据类型,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。


特点:

1.每个节点都只有有限个子节点或无子节点

2.没有父节点的节点称为根节点

3.每一个非根节点有且只有一个父节点

4.除了根节点外,每个子节点可以分为多个不相交的子树

5.树里面没有环路(cycle)


术语(Terminology):

根(Root) - 树中最顶端的节点,该节点没有父节点

子节点(child) - 一个节点含有的子树的根节点称为该节点的子节点

父节点(Parent) - 若一个节点含有子节点,则这个节点称为其子节点的父节点

兄弟节点(siblings) - 具有相同父节点的节点互称为兄弟节点

邻居节点(neighbor) - 父节点或者子节点

子孙节点(descendant) - 以某节点为根的子树中任一节点都称为该节点的子孙

祖先节点(ancestor) - 从根到该节点所经分支上的所有节点

叶节点(leaf) - 该节点没有子节点,即度为零的节点

分支节点(branch) - 该节点至少包含一个子节点,即度不为0的节点

度(degree) - 一个节点含有的子树的个数称为该节点的度

树的度 - 即根节点的度

边(edge) - 连接节点

距离(distance) - 两个节点最短距离经过的边数

深度(depth) - 节点与根节点的距离

层次(level) - 节点到根节点的边数+1

高度(height) - 节点到叶的最大边数

宽度(width) - 一个层次的节点数

树的高度 - 根节点到叶的最大边数

森林(forest) - 不相交树集合

子树(sub tree)

树的大小(size of tree) - 节点数



树的种类:

无序树(unordered tree) - 树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树

有序数(ordered tree) - 树中任意节点的子节点之间有顺序关系

二叉树(binary tree) - 每个节点最多含有两个子树

完全二叉树(complete binary tree) - 除了最后一层,其它各层的节点数目均已达最大值,且最后一层的所有节点从左向右连续地紧密排列,下图不是满二叉树


满二叉树(full binary tree) - 所有叶节点都在最底层,除了叶子节点之外,每个节点都有左右两个子节点(形状上是一个三角形)


平衡二叉树(balanced binary tree) - 任何节点的两棵子树的高度相差不大于1





上一篇: 队列
下一篇: 二叉查找树
作者邮箱: 203328517@qq.com