常州集训Day4

上午

今天早上讲了数据结构，树的存储，遍历，（完全）二叉树。

还有 最近公共祖先LCA——倍增法，对！就是我们所熟知的树链剖分/重链剖分！（省选内容）

树可以反映一对多的关系

树的存储

括号表示法/广义表

(1(2(5,6),3,4(7(8,9))))
括号括住层数，子树用逗号隔开

邻接矩阵和邻接表（儿子表示法）

以图存树，图论博客会详细说明

父亲表示法

记录自己的父亲

“完全二叉树”表示法（数组建树）

使用完全二叉树的性质建树（见后文）

指针方式存储（动态建树）

struct node
{
    node *parent;//父结点
    node *lchild;//左孩子
    node *rchild;//右孩子
    int data;//数据域
};
node *bt;//根结点
void pre_crt(node *&bt)
{
    cin >> ch;
    if(ch == 0) bt = NULL;//空树
    else
    {
        bt = new node;
        bt->data = ch;
        pre_crt(bt->lchild);//建左子树
        pre_crt(bt->rchild);//建右子树
    }
}

树的遍历

先序遍历：根左右

后序遍历：左右根

层序遍历：队列，类似广搜

中序遍历（只有二叉树有）：左根右

二叉树的性质

• 二叉树的第i层，最多有2^{i-1}个节点
• 深度为k的二叉树，最多有2^{k}-1个节点
• 二叉树的形态计数：

  1.定义F(n)：n个节点的二叉树的形态总数

  2.得：F(0)=1,F(1)=1,F(2)=2,F(3)=5

  3.递推公式：

  i. \sum_{i=0}^{n-1} F(i)*F(n-i-1)

  ii. \frac{C^n_{2n}}{n-1}

完全二叉树的性质

• $n$个节点的完全二叉树深度为：$log_{2}{n+1}$

• 关于在完全二叉树中编号为i的节点，其父节点编号为\lfloor \frac{i}{2} \rfloor ，其左子节点编号为2i，右子节点编号为2i+1

下午

下午讲了哈夫曼树，字典树，表达式树