二叉树
树
树是n个结点的有限集合,若n=0,则该树为空树。该集合需要满足以下条件才能被称为树:
对于任意一个非空树,
(1)有且只有一个根结点,也就是第一层只有一个结点。
(2)当结点数量大于1时,根节点以外的节点可分为互不相交的有限集合。每一个集合本身也是一个棵树,并称为根结点的子树。
下图所示是一个完全二叉树,用于理解层、深度等名词的概念。其中A、B结点拥有两颗子树,因此它的度为2;C节点无子树,度为0。
二叉树
二叉树是一种特殊的树,具有如下特点:
1.每个节点最多有两棵子树,结点的度取值只能为0、1、2。
2.二叉树的子树是区分左右的,即使结点只有一个子树,也要区分它是左子树还是右子树。
二叉树的五种基本形态:
(1)空子树 ,为了方便表示用没有编号的圈圈来表示,实际上空树的定义是一个结点也没有。
(2) 只有一个根结点
(3)根结点只有左子树
(4)根结点只有右子树
(5)根结点有左子树和右子树
几种特殊的二叉树
1.完全二叉树
除了最下层,其余每层的结点数都达到了最大值,且最下层的叶子节点从最左位置开始排列。
2.满二叉树
每一层的结点数都达到了最大。满二叉树一定是完全二叉树,完全二叉树不是满二叉树,除非该完全二叉树的倒数第二层的每个结点的度数都为2。
下图用于理解以上两个概念: