数据结构与算法-树

抽象数据类型定义

若|D|=0，则称为空树；
否则:
(1) 在D中存在唯一的称为根的数据元素root,
(2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm,其中Ti本身是一棵符合本定义的树，称为根root的子树。
例如：A是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}； T2={C,G}；T3={D,H,I,J,M}；T1，T2，T3都是根A的子树，且本身也是一棵树。

表示方法

• 图

• 凹入表示法

• 嵌套集合表示法

• 广义表

基本术语

• 结点：数据元素+若干指向子树的分支
• 结点的度：分支的个数
• 树的度：树中所有结点的度的最大值
• 叶子节点：度为零的结点
• 分支(非终端)结点：度大于零的结点
• (从根到结点的)路径：由从根到该结点所经分支和结点构成
• 祖先结点、双亲结点、兄弟结点、堂兄弟节点、孩子结点、子孙结点：
• 结点的层次：假设根结点的层次为0,第 i 层结点的子树的根结点的层次为 i
• 树的深度：树中叶子结点所在的最大层次
  
• 有向树：(１) 有确定的根；(２) 树根和子树根之间为有向关系
• 有序树：子树之间存在确定的次序关系
• 无序树：子树之间不存在确定的次序关系
• 森林：是 m（m≥0）棵互不相交的树的集合
• 任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点，F 被称为子树森林

结构特点

线性结构	树型结构
第一个数据元素无前驱	根结点（无前驱）
最后一个数据元素(无后继)	多个叶子结点(无后继)
其它数据元素(一个前驱、一个后继)	其它数据元素(一个前驱、多个后继)