二叉树 | 定义、性质、操作

内容参考自胡凡，曾磊 《算法笔记》

二叉树的递归定义

1. 递归边界：二叉树没有根结点，是一棵空树。
2. 递归式：二叉树由根结点，左子树，右子树构成，且左、右子树都是二叉树。

二叉树 vs 度为2的树：树的子树并无左右子树的分别，而二叉树的左右子树是严格区分的。

两种特殊的二叉树

满二叉树

每一层的结点个数都达到了当层能达到的最大结点数。

完全二叉树

1. 除最下面一层外，每一层的结点个数都达到了当层能达到的最大结点数。
2. 最下面一层只从左至右连续存在若干结点，而这些连续结点右边的结点全都不存在。

几个重要概念

层次
父亲结点、孩子结点
兄弟结点
祖先结点、子孙结点：⚠️祖先结点/子孙结点包括该结点自身。

二叉树的存储、基本操作

struct Node {
    int data; //数据域
    Node *lchild, *rchild; //指针域
};
Node *root = nullptr;

• 建树

• 查、改（递归）

void search（Node* root，int x， int newdata）

1. 边界：root == NULL / 找到
2. 递归式：分别递归当前root的左子树，右子树。

• 插入结点

1. 插入的位置就是查找失败的位置。
2. ⚠️insert（Node* &root， int x）
   根结点指针root必须传引用，因为不仅仅修改了指针指向的内容（*的作用），还修改了指针本身。

• 删

⚠️如何判断是否需要加引用
如果函数中需要新建结点，即对二叉树结构做出修改，就需要加引用；
如果仅仅修改当前已有结点内容（用指针）/仅仅遍历树，则不需要加引用。
⚠️ 新建结点之后，务必令新结点的左右指针域为NULL
⚠️ 判定结点存在否 root == NULL

完全二叉树的存储

设完全二叉树最大高度 k。
所有结点从上到下，从左到右从1开始编号
则编号n的结点若有左右孩子则编号分别为 2n、2n+1
完全二叉树可以用一个大小为2^k的数组存放。存放顺序即该完全二叉树的层序遍历序列。
编码时将数组大小设为结点上限个数+1即可。

• 判断 x 是否是叶结点：2x > n（没有左孩子，否）
• 判断 x 是否是空结点：x > n