学习笔记——二叉树

二叉树 binary tree,BT

一种特殊的树形结构，是度数为 2 的树。即二叉树的每个节点最多具有两个子节点，每个节点的字节点分别称为左孩子、右孩子，子树则为左子树，右子树。
二叉树可以为空且一定有序。
在二叉树的第 i 层上至多有 2ⁱ个节点 (i>=0)。
深度为 m 的二叉树上至多有 $\frac{1-2^{m+1}}{1-2}=2^{m+1}-1$ 个节点 (m>=0)，一棵深度为 m 且有 $2^{m+1}-1$ 个节点的二叉树被称为满二叉树。
每一个节点都与深度为 m 的满二叉树中编号为 1~n 的节点一一对应的深度为 m，有 n 个节点的二叉树被称为完全二叉树。
对于任意一棵二叉树，若其有 n₀个叶节点，n₂个度为 2 的节点，则一定有 n₀=n₂+1。
具有 n 个节点的完全二叉树的深度是 $floor\left( \log _2n \right)$ 。
在有 n 个节点的完全二叉树中，对于编号为 i 的节点：
- 若 $i=1$ ，则其无父节点，为根节点，否则其父节点编号为 $floor\left( \frac{i}{2} \right)$ 。
- 若 $2i>n$ ，则 i 为叶节点，否则其左孩子的编号为 2i。
- 若 $2i<n<2i+1$ ，则 i 无右孩子，否则其右孩子的编号为 2i+1。

如下图即二叉树示意图：

CPP

struct node {
    int data; //数据域
    node* lc, rc; //分别指向左孩子于右孩子
};
struct bt {
    node* root;
}t;

与树一样，其实就是孩子表示法。

CPP

struct node {
    int data; //数据域
    node* lc, rc; //分别指向左孩子于右孩子
    node* father; //指向父节点
};
struct bt {
    node* root;
}t;

同理，其实就是父亲孩子表示法。

如下图所示：

具有 n (n>=1 且 n 为整数) 个节点的二叉树的种类的数量可以用下方的函数来表示：

f\left( n \right) =\begin{cases} \sum_{i=0}^{n-1}{f\left( i \right) \cdot f\left( n-i-1 \right)}& \left( n>1 \right)\\ 1& \left( 0\leqslant n\leqslant 1 \right)\\ \end{cases}

这是第二篇学习笔记，上一篇可以点击这里查看。