树和二叉树的基本概念和性质

树

重要概念

• 树是递归定义的
  
• 节点的度：一个节点含有子树的个数称为该节点的度，如图中节点R的度为3
  
• 叶节点/终端节点：度为零的节点称为叶节点/终端节点，如图中的节点e，f，g，i……
  
• 分支节点：度不为零的节点
  
• 子节点：一个节点含有的子树的根节点称为该节点的子节点，如图中，m，n是h的子节点
  
• 父节点/双亲节点：若一个节点含有子节点，则称这个节点为该子节点的父节点/双亲节点，如图中，d是j，k的父节点
  
• 兄弟节点：具有相同的父节点互称为兄弟节点
  
• 树的度：一棵树中，最大的节点的度称为该树的度，如图中，该树的度为3
  
• 节点的层次：从根开始定义起，根为1，根的子节点为2，以此类推
  
• 树的高度/深度：树中节点的最大层次，如图中，该树的深度为4
  

tips：结点的层次也可以从零开始计算，但若如此，当树为空树时，树的高度为-1，不符合习惯，因此推荐从1开始算

树和非树

是树的必要条件

• 子树不能相交
  
• 除根节点外，每个子节点有且仅有一个父节点
  

二叉树

二叉树的特点

• 每个节点最多有两棵子树，即该树不存在度大于2的节点
• 二叉树的子树有左右之分，不能随意颠倒

满二叉树与完全二叉树

• 满二叉树：每一层的节点数都达到最大值。即，如果二叉树的层数为k，则节点总数是2^k-1
  
• 完全二叉树：是由满二叉树引出来的，假设一完全二叉树的高度为k，则其前k-1个层，节点达到最大值，第k层，节点未达到最大值，但节点从左往右都是连续的

• 完全二叉树中，只能存在一个度为1的节点
  
• 如，此二叉树就不是完全二叉树（因为最后一层节点不是从左往右连续存放）
  
  

• 满二叉树是特殊的完全二叉树
  

二叉树的性质

• 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点（即满二叉树的最后一层）
• 若规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^h-1(即满二叉树的节点数)
• 若规定根节点的层数为1，则具有n个节点的满二叉树的深度h = LogN（推导：n=2^h-1 -> 2^h=n+1 -> h=log₂(n+1)）
• 对任何一棵二叉树，如果度为零结点个数为n0，度为二的结点个数为n2，则有关系式：n0 = n2 + 1

二叉树存储形式

链式存储

• 链式存储就是指用链来表示一棵二叉树
• 通常的方法是链表中每个节点由三个域组成：数据域和左右指针域，这是我们常用的二叉链。

• 当然还有更高级，更复杂的三叉链，在二叉链的基础上多加了一个指向父节点的指针域

二叉链

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode *left;  //指向左子树
    struct BinaryTreeNode *right; //指向右子树
}BTNode;

三叉链

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode *left;  //指向左子树
    struct BinaryTreeNode *right; //指向右子树
    struct BinaryTreeNode *parent;  //指向父节点
}BTNode;

顺序存储

• 顺序结构存储就是使用数组来存储，即用层序的思想将二叉树的节点依次存入数组
  
• 一般使用数组只适合表示完全二叉树，因为如果不是完全二叉树会造成空间的浪费
  
• 在实际的使用中，只有用到堆的时候才会用数组来存储二叉树，例如堆排序
  
• 要明确的一点是，二叉树的顺序存储在物理结构上是一个数组，在逻辑结构上是一棵二叉树。