二叉树基础

二叉树的定义

二叉树是一种特殊的树。

这是二叉树的递归定义：

二叉树要么为空，要么由根节点、左子树和右子树组成，左子树和右子树也是二叉树。

二叉树的性质

二叉树的普适性质

1.在二叉树的第i层上最多有\(2^{i-1}\)个节点

2.深度为k的二叉树的节点数最多为\(2^k-1\)

3.\(n_0 = n_2 + 1\),\(n_i\)表示度为i的节点。

特殊二叉树的性质

1.完全二叉树

完全二叉树的定义：

若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h层所有的结点都连续集中在最左边，这就是完全二叉树

完全二叉树的特点：

(1)只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的层上出现

(2)

对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

2.满二叉树

定义：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

满二叉树可以看做是特殊的完全二叉树，即满二叉树一定是完全二叉树，反过来则未必。

二叉树的指针存储法

为什么要用指针建树？

因为用指针建立的树是略快于数组建立的树的，虽然差距不是很大，但还是有差距的。

指针建树的原理

和链表一样。（后续补充

基本结构介绍

struct Node{    int val;    Node *left, *right;    Node():left(NULL), right(NULL){};//构造函数};Node* root;//根节点

由此方法建立的二叉树每次需要一个新的节点(Node)时，都要用new运算符

申请内存，并执行构造函数。

这是一个将申请新节点封装到函数(newnode)中的例子

Node* newnode(){return new Node();}

指针的内存问题

如果建立起一棵树后，执行root = newnode()，那么从前申请的内存就再也无法访问到了，但是那些内存并没有被释放，这叫内存泄漏(memory leak)。

释放二叉树内存的例子

void delete_tree(Node* u) {if(u == NULL) return;delete_tree(u -> left);delete_tree(u -> right);//至于为什么采用这样的顺序……delete u;

参考代码

#include
    
     using namespace std;struct Node{    char val;    Node *lc, *rc;    Node():lc(NULL), rc(NULL){};};Node* root;Node* build() {    char c;    cin >> c;    if(c == '.') return NULL;        Node* u = new Node();    u->val = c;        u->lc = build();    u->rc = build();        return u;}void mid(Node* u) {    if(u == NULL) return;    mid(u->lc);    cout << u->val;    mid(u->rc); }void next(Node* u) {    if(u == NULL) return;    next(u->lc);    next(u->rc);    cout << u->val;}void delete_tree(Node* u) {    if(u == NULL) return;    delete_tree(u->lc);    delete_tree(u->rc);    delete u;}int main() {    root = build();        mid(root);    cout << '\n';    next(root);        delete_tree(root);//释放空间         return 0;}

下面是花式建树

这是一份正常的线段树代码。

#include
    
     #include
     
      using namespace std;struct Node{    int l, r;    long long val, tag;    Node *lc, *rc;        Node(int x, int y, long long v, long long t, Node* a, Node* b) {        l = x;        r = y;        val = v;        tag = t;        lc = a;        rc = b;    }};Node* root;int opt, x, y;long long k, a[100001];Node* build(int l, int r) {    if(l == r) return new Node(l, r, a[l], 0, NULL, NULL);        int mid = (l + r) >> 1;        Node *left = build(l, mid), *right = build(mid+1, r);        return new Node(l, r, left->val + right->val, 0, left, right);    }inline void pushdown(Node* &u) {    if(u->l == u->r) {        u->tag = 0;        return;    }        int mid = (u->r + u->l) >> 1;        u->lc->val += (mid - u->l + 1) * u->tag;    u->rc->val += (u->r - mid) * u->tag;        u->lc->tag += u->tag;    u->rc->tag += u->tag;        u->tag = 0;}void modify(int l, int r, Node* &u) {    if(u->tag) pushdown(u);        if(l == u->l && r == u->r) {        u->val += (r - l + 1) * k;        u->tag += k;        return;    }        int mid = (u->l + u->r) >> 1;        if(r < mid+1) modify(l, r, u->lc);    else if(l > mid) modify(l, r, u->rc);         else {            modify(l, mid, u->lc);            modify(mid+1, r, u->rc);         }        u->val = u->lc->val + u->rc->val;}long long query(int l, int r, Node* &u) {        if(u->tag) pushdown(u);        if(l == u->l && r == u->r) return u->val;        int mid = (u->l + u->r) >> 1;        if(r < mid+1) return query(l, r, u->lc);    if(l > mid) return query(l, r, u->rc);        return query(l, mid, u->lc) + query(mid+1, r, u->rc);}int main() {    int n, m;    scanf("%d%d", &n, &m);        for(register int i = 1; i <= n; ++i)        scanf("%lld", &a[i]);    root = build(1, n);    for(register int i = 1; i <= m; ++i) {        scanf("%d", &opt);        if(opt == 1) {            scanf("%d%d%lld", &x, &y, &k);            modify(x, y, root);        }        else {            scanf("%d%d", &x, &y);            printf("%lld\n", query(x, y, root));        }    }        return 0;}

重写了一遍，可以更好地用作参考。

21:48 5.21. 2019.