【软件设计师：数据结构】2.数据结构基础（二）

一、树

树是n(n≥0)个结点的有限集合，n=0时称为空树，在任一非空树中

● 有且仅有一个称为根的结点。

● 其余的结点可分为m(m≥0)个互不相交的子集T1，T2…，Tm，其中每个子集本身又是一棵树，并称其为根结点的子树。

1、树的基本概念

● 双亲和孩子

● 兄弟：具有相同双亲的结点互为兄弟。

● 结点的度：一个结点的子树的个数记为该结点的度。

● 树的度：树中各结点的度的最大值

● 叶子结点：也称为终端结点，指度为零的结点。

● 内部结点：度不为零的结点称为分支结点或非终端结点。除根结点之外，分支结点也称为内部结点。

● 结点的层次：根为第一层，根的孩子为第二层，依此类推。

● 树的高度：一棵树的最大层次数记为树的高度（或深度）。

● 有序（无序）树：若将树中的结点的各子树看成是从左到右具有次序的，即不能交换，则称该