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

1.二叉树的概念

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

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

• 由图可知二叉树的每个节点的度==不超过2==

• 二叉树分为左子树和右子树，==二叉树是有序树==

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

  

2.特殊二叉树

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

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

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

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

   

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

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

• 完全二叉树是钱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~0~, 度为2的分支结点个数为n~2~,则有 n~0~＝ n~2~＋1

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

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，==h= log~2~(n+1)==. (ps： 是log以2 为底，n+1为对数)

5. 对于具有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意味着超过了最大的序号数

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