二叉树的性质

1.在二叉树的第i层上至多有$2^{i-1}$个节点 2.深度为k的二叉树至多有$2^k-1$个节点 >满二叉树：深度为k且有$2^k-1$个节点的二叉树，每层上的节点数都是最大节点数。

3.任意二叉树，若叶节点数为$n_0$度为2的节点数为$n_2$则必有$n_0=n_2+1$ 4.具有n个节点的完全二叉树深度为floor($log_2 10$) 5.对于一棵n个节点的完全二叉树，对任意一个节点有 >1.若i=1，则i为根，无父节点。若i》1，则父节点编号为i/2。若2i>n，则i无左孩子，也无右孩子，否则做孩子编号为2i 2.若2i+1>1，则i无右孩子，否则右孩子编号为2i+1

二叉树遍历方法

·先序遍历，即先遍历根节点，再遍历左节点，最后是右节点。 ·中序遍历，即先遍历左节点，再遍历根节点，最后是右节点。 ·后序遍历，即先遍历左节点，然后是右节点，最后是根节点

注意，遍历时若条件允许，应考虑递归实现，便于理解。辅助栈+while的方式不太便于理解，但须加强对此的理解

已知先序，中序 遍历结果，求后序结果样例解析(一本通P432)

    string s1,s2;//s1先序s2中序
    void cacl(int l1,int r1,int l2,int r2){
    int m = find(s2[l1]);//找到先序遍历的根节点在中序遍历中的位置
    if(m>l2)cacl(l1+1,l1+m-l2,l2,m-1);//递归建树，元素为l1+1(l1已结计算过了)
    //位置[l1+1,l1+长度]长度即是m的位置-初始位置
    if(m<r2)cacl(l1+m-l2+1,r1,m+1,r2);//同上
    cout<<s1[l1];//输出就行
    }

拓展二叉树

即把空节点用.表示。这样以后，就可以通过先序或者后序序列构建整颗二叉树。代码

略

普通树转二叉树

说白了就是自己看情况，不记

相似二叉树

两者都为空熟或者均不为空疏，且左右自树分别相似。 等价二叉树即不仅相似，而且所有对应节点上的元素均相等。 SUM of similar binary tree: $B_0 = 1$ $b_n=\sum_{i=0}^{n=1}B_iB_{n-i-1}$

完全二叉树

一颗深度为k的二叉树，1至k-1层的节点都是满的，即满足$2^{i-1}$，只有最下面的一层的节点数小于$2^{i-1}$,并且最下面一层的节点都集中在该层最左边若干位置，则次二叉树称为完全二叉树

堆的性质

1.设数组A的长度为len，二叉树的节点个数为size，则size<=len，A[i]储存二叉树中编号为i的节点值。A[size]以后的元素不属于相应的堆，树的根为[1]，并且很容易求得i的父节点的编号为i/2，左子节点为2i，节点为2i+1； 2.对于除根以外的每个节点，父节点的节点值大于等于该节点。即A[parent(i)]>=A[i]。除根节点以外，所有节点的值都不超过父节点的值，可以退出，堆中最大的元素放在根节点中。若每一节点的子树的节点值小于等于该节点的堆叫大根堆。反之，若除根以外的每个节点i都有A[parent(i)]<=A[i]的堆，叫小根堆。

求完全二叉树(堆)的父节点

$\frac{i}{2}$

建堆

1.put一个元素//一本通P442

1.在堆尾加入一个元素，并把这个节点设置为当前节点 2.比较当前节点和它父节点的大小 若当前节点小于父节点，则交换它们的值，并把父节点(就是加入的那个元素所在的节点)设置为当前节点，转到2； 若大于父节点等于，转到3 3.结束

2.从堆中取出一个元素

(1)取出堆的根的值 (2)将最后一个节点len放到根的位置上，覆盖掉堆，堆长度减一 (3)把根节点(刚才的len)置为当前的父节点pa (4)如果pa无儿子(fa>len/2)则转6，否则把pa的两个儿子中最小的那个置为当前的子节点son (5)比较pa与son的值 若pa小于等于son，转6，否则，交换两个节点的值，把pa指向son，转4 (6)结束

STL的heap

在头文件里面 4个函数 make_heap(_First,_Last,cmp); make_heap(_First,_Last);大根堆 一般对于int类型，cmp可以为greate()得到小根堆 push_heap(_First,_Last); 讲一个元素放入堆中 pop_heap(_First,_Last) 调用此函数删除数据 sort_heap(_First,_Last) 排序堆，排序 之后不是合法的堆。

FINALLY

建堆和put与get操作的时间复杂度是O($log_2n$),建堆操作是O($nlog_2n$)，于是乎一个便于维护，且复杂度较低的数据结构就解决啦

树的重心

如果我们挑选某个节点为树的根结点的话，剩下的各个子树大小会相对接近，这就是树的重心 可以用于树的分治算法。 重心的性质：

求重心

1.先dfs一下，求出以每个点为根节点的子树大小

树的直径

树的直径就是一棵树上最长的一条链 1.dfs，详见洛谷网课 2.dp，