树与二叉树的基本知识点

文章目录

一、树

二、二叉树

三、树和二叉树的2个主要差别与二叉树的特点

四、特殊的二叉树

五、二叉树的性质

一、树

• 树是n（n>=0）个结点的有限集。n=0为空树
• 当n>1时，结点分为m个互不相交的有限集，每一个集合又是一棵树，称为根的子树。
• n>0时，根节点唯一
• m>0时，子树个数没有限制，但是它们一定是互不相交的！
  
• 结点的度：结点拥有的子树（结点下面的分叉条数）
• 叶节点：也叫终端结点，度为0的结点
• 分支结点：也叫非终端结点，度不为0的结点（除根节点外，分支结点也称为内部结点）
• 树的度：树内所有结点中度的最大值
• 结点的祖先：从根到该结点所经分支上的所有结点。（对于H来说，D、B、A都是它的祖先）
  
  树的深度（高度）：树种结点的最大层次
  

二、二叉树

• 二叉树：n（n>=0）个结点的有限集合
• 或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

三、树和二叉树的2个主要差别

• 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
• 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。
• 注意：二叉树不是树的特殊情形！尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

二叉树的特点：

• 一、每个结点最多有两颗子树（0，1，2）
• 二、左子树和右子树是有顺序的，次序不能颠倒
• 三、即使树中某结点只有一颗子树，也要区分左和右
  
  例子：三个结点五中形态的二叉树
  

四、特殊的二叉树

• 一、斜树：所有结点只有左子树叫左斜树，右斜树同理

• 二、满二叉树（完美二叉树）：所有分支结点都存在左、右子树，所有叶子在同一层上
  在同样深度的二叉树中，满二叉树结点个数最多，叶子数最多
  

• 三、完全二叉树：结点跟满二叉树上对应位置编号完全相同（从左到右数，不能间断）
  1、叶子结点只能出现在最下两层
  2、最下层叶子集中在左边连续位置，倒数两层，叶子结点集中在右边连续位置
  3、结点度为1的结点只有左孩子
  4、同样结点数的二叉树，完全二叉树的深度最小
  以下都不符合完全二叉树的标准：
  

五、二叉树的性质

• 一、第i层上最多有2^（i-1）个结点

• 二、深度为k的二叉树，总结点数为2^k-1（看清没括号！）

• 三、如果叶节点数（度为0）为n0，度为2的结点数为n2，得n0=n2+1

• 四、具有n个结点的完全二叉树深度为【log2n】+1（【x】表示不大于x的最大整数）

• 五、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序 不发生改变

• 总结点数为n，分支线总数为n-1
• 总结点数n=n0+n1+n2
• 分支线总数n-1=n1+2n2。
• 推导出n0=n2+1
• 完全二叉树度为1的节点只能有0个或1个（不信可以画画看一下）

例题： 具有1102个结点的完全二叉树一定有__个叶子结点。

• 设n2为度为2的节点，n1为度为1的节点，n0为度为0的节点；
• 边数n=节点数-1，即n=1101；
• n=2*n2+n1;
• 完全二叉树度为1的节点只能有0个或1个（不信可以画画看一下）
• 所以n1=0或者1用n=2*n2+n1;算一下，n2肯定是整数，把0舍去；
• 求出n2=550；
• 度为0的节点数等于度为2的节点数+1；
• 所以叶子节点数为551