5.1二叉树——基本概念梳理

本篇博客梳理二叉树相关的基本概念

一、树的概念与结构

1．树是递归定义的

树==根+N棵子树，每棵子树也可按照相同方式拆分
注意：子树之间不能有交集，否则变成图（是另一种数据结构）

2．树的相关概念

（1）结点的度：一个结点含有的子树（子结点）的个数；A的度为6
（2）叶节点/终端结点：度为0的结点；如B,C,H,I,L,M,N
（3）双亲结点/父结点：如E是I和J的父节点
（4）孩子节点/子结点：如I，J是E的子节点
（5）树的高度/深度：图中树的高度为4

3．树的表示

（1）要求：既要保存值域，也要保存结点之间的关系
（2）左孩子右兄弟表示法
此方法可以高效地找到一个节点的所有子节点

typedef int DataType; 
struct Node 
{ struct Node* firstChild1; // 第一个孩子结点 struct Node* pNextBrother; // 指向其下一个兄弟结点 DataType data; // 结点中的数据域 
};

二、二叉树的概念与结构

假设树的高度为h，结点数为N

1．概念

子结点最多两个（度最大是2）

2．特殊的二叉树

（1）完全二叉树
①前（h-1）层为满二叉树
②最后一层不满，且最后一层从左到右必须连续
（2）满二叉树（特殊的完全二叉树）：每层的节点数都达到最大

3．满二叉树的性质

深度为h的树，有
逻辑：第一层0个结点，即2^0；第二层1个结点，即2 ^ 1;以此类推，最终用等比数列求和可得结果

4．二叉树的存储结构

（1）顺序存储：用数组来存储
①只适合表示完全二叉树，如果不是完全二叉树会有空间浪费

②物理上：是一个数组；逻辑上：是一棵二叉树
③父子之间的坐标关系（设父亲下标为i）
左孩子下标：2i+1
右孩子下标：2i+2
反之：若左孩子下标为j，可求得父结点坐标为**（j-1）/2**
（2）链式存储：用链表来存储——数据域+左右指针域

typedef int BTDataType; 
// 二叉链 
struct BinaryTreeNode 
{ struct BinTreeNode* left; // 指向当前结点左孩子 struct BinTreeNode* right; // 指向当前结点右孩子 BTDataType data; // 当前结点值域 
}