数据结构之二叉树基本概念与性质

1.二叉树的概念

1.一棵二叉树是结点的一个有限集合该集合:

2.或者为空 ，由一个根节点加上两棵别称为左子树和右子树的二叉树组成

• 由图可知二叉树的每个节点的度不超过2
  
• 二叉树分为左子树和右子树，二叉树是有序树

任意的二叉树都由基本的几个情况复合而来

2.特殊二叉树

1. 满二叉树：一个二叉树，如果每个层的结点数达到最大值那么这就是一个满二叉树。

也就是说如果一个树k层的话，这个树有2^k-1个结点数，那么这就是满二叉树

1. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。满二叉树是一种特殊的完全二叉树

完全二叉树的节点都要是连续的！

1. 这就是一颗完全二叉树！每个结点都是联系的！

这就不是一颗完全二叉树因为结点不连续！

• 完全二叉树是钱k-1层是满的，最后K层不一定满所以节点的数量为[2^k-1,2^k-1]
  
• 关于二叉树的层数，有的是从0开始，有的是从1开始，一般都是从1开始，这样子空树就规定为0，若是从0开始，则空树就要规定为-1。
  

3.二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
   
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1
   
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n₀, 度为2的分支结点个数为n₂,则有 n₀＝ n₂＋1

这是一个很重要的性质！对于二叉树而言叶子节点的个数永远比度为2的节点的个数+1.

1. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log₂(n+1). (ps： 是log以2 为底，n+1为对数)
   
2. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
   
2. 2i+1<n，左孩子的序号为2i+1，若2i+1>=n，则说明无左孩子

2i+1>= n意味着超过了最大的序号数

1. 2i+2<n，右孩子的序号为2i+2，若2i+2>=n，则说明无右孩子