学习笔记——二叉树

AI摘要
加载中...
摘要由AI自动生成,仅供参考!

二叉树binary tree,BT

介绍

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

如下图即二叉树示意图:

存储结构

单链表结构
1
2
3
4
5
6
7
struct node {
int data; //数据域
node* lc, rc; //分别指向左孩子于右孩子
};
struct bt {
node* root;
}t;

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

双链表结构
1
2
3
4
5
6
7
8
struct node {
int data; //数据域
node* lc, rc; //分别指向左孩子于右孩子
node* father; //指向父节点
};
struct bt {
node* root;
}t;

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

遍历

  • 先序遍历(输出->左孩子->右孩子)
  • 中序遍历(左孩子->输出->右孩子)
  • 后序遍历(左孩子->右孩子->输出)

普通树转二叉树

  1. 对于每一个节点,去除除最左边的树枝之外的所有树枝。
  2. 从最左边的节点开始,依次次将同层的每个兄弟节点横向相连。
  3. 以根节点为中心,将图形顺时针旋转约45°。

如下图所示:

树的计数

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

f(n)={i=0n1f(i)f(ni1)(n>1)1(0n1)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}

题外话

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


学习笔记——二叉树
https://www.ordchaos.com/posts/340b325e/
作者
序炁
发布于
202271
更新于
202271
许可协议