易混淆的概念

树的性质的常见考点

• 节点数=总度数+1
• 度为m的树VS m叉树
  
  
  

考点6和考点4是一个反解关系

树，森林

树的存储结构

双亲存储表示法（顺序存储）

孩子表示法（顺序+链式）

孩子兄弟法

左孩子右兄弟

树，森林，二叉树的转化

秉承左孩子右兄弟
==森林中的叶节点的个数等于对应二叉树的左孩子指针为空的节点个数==

树和森林的遍历

树的遍历

森林的遍历

二叉树

概念

可为空树，左右子树不可颠倒

二叉树 VS 度为2的树：

  1. 度为2的树结点个数至少是3个
       2. 度为2的树如果只有一个孩子，这个孩子无须区分左右，但是二叉树左右孩子的次序是固定的

特殊二叉树

• 满二叉树：所有叶子节点都在二叉树的最下一层
• 完全二叉树：与满二叉树编号相同的子树
  
• 二叉排序树（二叉查找树）（BST）：左子树上的所有结点的关键字均小于根节点
• 平衡二叉树（AVL）：在二叉排序树的基础上，左右子树深度之差不超过1

二叉树的性质：

• n0=n2+1
• 二叉树的第i层最多2的i-1次方个结点
• 高度为h的二叉树最多有2的h次方-1个结点

完全二叉树的性质：

• 完全二叉树最多只会有一个度为一的结点
• 编号为i的左儿子为2i，右儿子为 2i+1
• 完全二叉树的最后一个分支节点的序号为n/2向下取整

二叉树的存储结构

顺序存储结构：（比较适合完全二叉树，不然太浪费空间了）

链式存储：