软考中级-数据库-3.3 数据结构-树

定义:树是n(n>=0)个结点的有限集合。当n=0时称为空树。在任一非空树中，有且仅有一个称为根的结点:其余结点可分为m(m>=0)个互不相交的有限集T1,T2,T3...,Tm…，其中每个集合又都是一棵树，并且称为根结点的子树。

树的相关概念

1、双亲、孩子和兄弟:

2、结点的度:一个结点的子树的个数记为该结点的度。

3、叶子结点:也称为终端结点，指度为零的结点。

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

5、结点的层次:根为第一层，根的孩子在第二层，依此类推。

6、树的高度:一棵树的最大层次数记为树的高度(或深度)。

7、有序(无序)树:若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。

8、森林:m(m>=0)棵互不相交的树的集合。

二叉树

定义:二叉树是n(n>=0)个结点的有限集合，它或者是空树(n=0)，或者是由一个根结点及两棵不相交的、分别称为左子树和右子树的二叉树所组成。

树和二又树的区别:(1)二叉树中结点的子树要区分左子树和右子树,即使只有一棵子树，而树中不用区分。(2)二叉树中结点的最大度为2，而树中无限制。