树的逻辑结构

一.树的定义

树：n($n>=0$n>=0)个结点的有限集合。当n=0时，称为空树。
任意一棵非空树满足以下条件：
1）有且仅有一个特定的结点称为根的结点
2）当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合$T_1,T_2,...,T_m$T1​,T2​,...,Tm​,其中每一个集合又是一棵树，并称为这个根结点的子树。

二.树的基本术语

结点的度：结点所拥有的子树的个数
树的度：树中各结点度的最大值
叶子结点：度为0的结点，也称为终端结点。
分支结点：度不为0的结点，也称为非终端结点。
孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点
兄弟：具有同一个双亲的孩子结点互称为兄弟。
路径：如果树的结点序列$n_1,n_2,...,n_k$n1​,n2​,...,nk​有如下关系：结点$n_i$ni​是$n_i+1$ni​+1的双亲（1<=i<k),则把$n_1,n_2,...,n_k$n1​,n2​,...,nk​称为一条由$n_i$ni​至$n_k$nk​的路径，路径上经过的边的个数称为路径长度。
祖先、子孙：在数中，如果有一条路径从结点x到结点y,则x称为y的祖先，而y称为x的子孙。
结点所在层数：根结点的层数为一，对其余任何结点，若某结点在第K层，则其孩子结点在第K+1层。
树的深度：树中所有结点的最大层数，也称高度。
层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编号以从1开始的连续自然数。
有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，无序树。
森林：m(m>=0)棵互不相交的树的集合。

在图6—1中，A是祖先，L则是它的子孙；树的高度为4；

三.树的抽象数据类型（ADT Tree)

Data
树是有一个根节点和若干棵子树构成，
数中结点具有相同数据类型及层次关系
Operation
InitTree:初始化一棵树
DestroyTree:销毁一棵树，释放内存空间
PreOrder:前序遍历
PostOrder:后续遍历

树的遍历：从根结点出发，按照某种次序访问数中所有结点，使得每一个结点被访问一次且仅被访问一次

前序遍历：
1.若树为空，则空操作返回
2.否则，访问根结点，按照从左到右的顺序前序遍历根节点的每一颗子树。
前序遍历上图：A B D E H I F C G

后序遍历：
1.若树为空，则空操作返回
2.按照从左到右的顺序后序遍历根节点的每一颗子树。
后序遍历上图：D H I E F B G C A

层次遍历：
从树的第一层（即根节点）开始，自上而下逐层遍历，在同一层中，按照从左到右的顺序对结点逐个访问。
层次遍历上图：A B C D E F G H I

四.树的存储结构

如何表示逻辑关系

三.树结构与线性结构的比较

	线性结构	树结构
第一个数据元素	无前驱	又称根节点（只有一个）：无双亲
最后一个数据元素	无后继	叶子结点（可以有多个）：无孩子
其他数据元素	一个前驱，一个后继	其他结点：一个双亲，多个孩子
关系	一对一	一对多