【学习笔记】数据结构（六 ①）

树和二叉树 （一）

文章目录

• 树和二叉树 （一）
• • 6.1 树(Tree)的定义和基本术语
  • 6.2 二叉树
  • • 6.2.1 二叉树的定义
    • • 1、斜树
      • 2、满二叉树
      • 3、完全二叉树
      • 4、二叉排序树
      • 5、平衡二叉树（AVL树）
      • 6、红黑树
    • 6.2.2 二叉树的性质
    • 6.2.3 二叉树的存储结构
  • 6.3 遍历二叉树和线索二叉树
  • • 6.3.1 遍历二叉树

6.1 树(Tree)的定义和基本术语

树(Tree)是n(n≥0)个结点的有限集。

在任意一棵非空树中:

​ (1) 有且仅有一个特定的称为**根(Root)**的结点;

​ (2) 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T₁,T₂,…,T_m,其中每一个集合本身又是一棵树,并且

​ 称为根的子树(SubTree)。

树的特点：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点可以有零个或多个后继。
3. 树中的结点数等于所有结点的度数加1.
   度为m的树中第i层上至多有m^i-1个结点（i > = 1）
   高度为h 的m叉树至多有( m^h − 1 ) / ( m − 1 )个结点。
   具有n个结点的m叉树的最小高度为[ log_m ( n ( m − 1 ) + 1 ) ] 。

树的其他表示形式：

​ ( a ) 是以嵌套集合(即是一些集合的集体,对于其中任何两个集合,或者不相交,或者一个包含另一个)的形式表示的;

​ ( b ) 是以广义表的形式表示的,根作为由子树森林组成的表的名字写在表的左边;

​ ( c ) 用的是凹人表示法(类似书的编目)。