数据结构第七讲：二叉树基本概念

返回目录

二叉树的定义

二叉树 或者是一棵 空树，或者是一棵由一个根节点和两棵互不相交的分别称做根节点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。这里注意，度为 2 的树不可能是空树，因此二叉树与度为 2 的树不同。

二叉树有如下性质：

• $n_{0}=n_{2}+1$；

• 节点度数之和$=n_{1}+2n_{2}=n-1$；

• 非空二叉树上第$i$ 层至多有$2^{i-1}$ 个节点；

• 高度为$h$ 的二叉树至多有$2^{h}-1$ 个节点；

满二叉树 每一层都满（第$i$ 层恰好有$2^{i-1}$ 个节点）时、，且叶子节点在同一层上。

• 满二叉树没有度为 1 的节点，即$n_{1}=0$。

完全二叉树 除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个节点。

• 完全二叉树至多只有最下边两层节点的度数小于 2。

• 按层序编号后对编号为$i$ 的节点，若$2i \leqslant n$，则是分支节点，否则是叶子节点。其父节点编号为$\lfloor \cfrac{n}{2} \rfloor$，左右子节点编号分别为$2i,2i+1$。

• 若$n$ 为奇数，则每个分支节点都既有左子节点，也有右子节点，也就是没有度为 1 的节点，即$n_{1}=0$；若$n$ 为偶数，则编号最大的分支节点只有左子节点，没有右子节点，其余分支节点都有左右子节点，也就是恰好有一个度为 1 的节点，即$n_{1}=1$。

完全二叉树或满二叉树采用 顺序存储结构 比较合适，既能够最大可能地节省存储空间，又可以利用数组元素的下标确定节点在二叉树中的位置以及节点之间的关系。典型的例子是线段树。

如果需要增加很多空节点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构，而是用 二叉链存储结构。典型的例子是动态开点线段树。

二叉链基础

template <typename T>
ostream& operator<<(ostream& os, const basic_string<T>& s) {
    for (auto& c : s) {
        os << c;
    }
    return os;
}

template <class T>
struct BinaryTree {
    struct node {
        T data;
        node* ls;
        node* rs;
        node* parent;
    };

    node* root;
    BinaryTree() {
        root = nullptr;
    }
    BinaryTree(const basic_string<T>& s) {  // 括号序
        stack<node*> stk;
        int op = 0;
        node* p = nullptr;

        root = nullptr;
        for (auto& c : s) {
            if (c == '(') {
                stk.push(p);
                op = 1;
            } else if (c == ')') {
                stk.pop();
            } else if (c == ',') {
                op = 2;
            } else {
                p = new node;
                p->data = c;
                p->ls = p->rs = nullptr;
                p->parent = stk.empty() ? nullptr : stk.top();
                if (root == nullptr) {
                    root = p;
                } else {
                    if (op == 1) {
                        stk.top()->ls = p;
                    } else {
                        stk.top()->rs = p;
                    }
                }
            }
        }
    }

    // 析构函数
    ~BinaryTree() {
        delete_subtree(root);
    }

    friend ostream& operator<<(ostream& os, const BinaryTree& bt) {
        auto dfs = [&](auto&& self, const node* p) -> void {
            if (p) {
                os << p->data;
                if (p->ls || p->rs) {
                    os << '(';
                    self(self, p->ls);
                    os << ',';
                    self(self, p->rs);
                    os << ')';
                }
            }
        };
        dfs(dfs, bt.root);
        return os;
    }

    void delete_subtree(node* p) {
        auto dfs = [&](auto&& self, node* p) -> void {
            if (p == nullptr) return;
            self(self, p->ls);
            self(self, p->rs);
            delete p;
        };
        node* q = p->parent;
        dfs(dfs, p);
        if (q) {
            if (q->ls == p) {
                q->ls = nullptr;
            } else {
                q->rs = nullptr;
            }
        } else {
            root = nullptr;
        }
    }
};

求二叉树的高度、大小、叶子树等

int height() {
    auto dfs = [&](auto&& self, const node* p) -> int {
        return p == nullptr ? 0 : max(self(self, p->ls), self(self, p->rs)) + 1;
    };
    return dfs(dfs, root);
}

int size() {
    auto dfs = [&](auto&& self, const node* p) -> int {
        return p == nullptr ? 0 : self(self, p->ls) + self(self, p->rs) + 1;
    };
    return dfs(dfs, root);
}

int leaves() {
    auto dfs = [&](auto&& self, const node* p) -> int {
        return p == nullptr ? 0 : (p->ls == nullptr && p->rs == nullptr) + self(self, p->ls) + self(self, p->rs);
    };
    return dfs(dfs, root);
}

二叉查找树

node* find(const T a) {  // 找a的子树
    auto dfs = [&](auto&& self, node* p) -> node* {
        if (p == nullptr) return nullptr;
        if (p->data == a) {
            return p;
        }
        if (auto q = self(self, p->ls)) {
            return q;
        }
        if (auto q = self(self, p->rs)) {
            return q;
        }
        return nullptr;
    };
    return dfs(dfs, root);
}

二叉树的形态

括号序代表了树的形态。

string shape() {
    auto dfs = [&](auto&& self, const node* p) -> string {
        return p == nullptr ? "" : '(' + self(self, p->ls) + ',' + self(self, p->rs) + ')';
    };
    return dfs(dfs, root);
}

二叉树拷贝

BinaryTree copy() {
    BinaryTree res;
    auto dfs = [&](auto&& self, const node* p, node* parent) -> node* {
        if (p == nullptr) return nullptr;
        node* q = new node;
        q->data = p->data;
        q->parent = parent;
        q->ls = self(self, p->ls, q);
        q->rs = self(self, p->rs, q);
        return q;
    };
    res.root = dfs(dfs, root, nullptr);
    return res;
}

Notes

A

#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;

using T = char;
struct BTNode {
    T data;
    BTNode* lchild;
    BTNode* rchild;
};

void DestroyBTree(BTNode*& bt) {
    auto dfs = [&](auto&& self, BTNode* p) -> void {
        if (p) {
            self(self, p->lchild);
            self(self, p->rchild);
            delete p;
        }
    };
    dfs(dfs, bt);
}

int BTHeight(BTNode*& bt) {
    auto dfs = [&](auto&& self, BTNode* p) -> int {
        return p == nullptr ? 0 : max(self(self, p->lchild), self(self, p->rchild)) + 1;
    };
    return dfs(dfs, bt);
}

int NodeCount(BTNode*& bt) {
    auto dfs = [&](auto&& self, BTNode* p) -> int {
        return p == nullptr ? 0 : self(self, p->lchild) + self(self, p->rchild) + 1;
    };
    return dfs(dfs, bt);
}

int LeafCount(BTNode*& bt) {
    auto dfs = [&](auto&& self, BTNode* p) -> int {
        return p == nullptr ? 0 : (p->lchild == nullptr && p->rchild == nullptr) + self(self, p->lchild) + self(self, p->rchild);
    };
    return dfs(dfs, bt);
}

void DispBTree(BTNode* bt) {  // 括号序输出
    if (bt != nullptr) {
        cout << bt->data;
        if (bt->lchild != nullptr || bt->rchild != nullptr) {
            cout << '(';
            DispBTree(bt->lchild);
            if (bt->rchild != nullptr) {
                cout << ',';
                DispBTree(bt->rchild);
            }
            cout << ')';
        }
    }
}

void CreateBTree(BTNode*& bt, char* str)    //由括号表示串创建二叉链
{
    BTNode* St[MaxSize], * p = nullptr;
    int top = -1, k, j = 0;
    char ch;
    bt = nullptr;            //建立的二叉树初始时为空
    ch = str[j];
    while (ch != '\0')    //str未扫描完时循环
    {
        switch (ch) {
            case '(':top++; St[top] = p; k = 1; break;    //为左孩子节点
            case ')':top--; break;
            case ',':k = 2; break;    //为右孩子节点
            default:p = new BTNode();
                p->data = ch; p->lchild = p->rchild = nullptr;
                if (bt == nullptr)    //*p为二叉树的根节点
                    bt = p;
                else            //已建立二叉树根节点
                {
                    switch (k) {
                        case 1:St[top]->lchild = p; break;
                        case 2:St[top]->rchild = p; break;
                    }
                }
        }
        j++;
        ch = str[j];
    }
}

int main() {
    char tree[MaxSize];
    cin >> tree;
    BTNode* bt;
    CreateBTree(bt, tree);
    DispBTree(bt);    cout << endl;
    cout << BTHeight(bt) << " " << NodeCount(bt) << " " << LeafCount(bt);
    DestroyBTree(bt);
    return 0;
}

B

int main() {
    string s;
    cin >> s;

    BinaryTree<char> bt(s);

    char a;
    cin >> a;
    bt.delete_subtree(bt.find(a));

    cout << bt << endl;

    return 0;
}

C

#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;

typedef struct BTNode {
    ElemType data;
    struct BTNode* lchild, * rchild;
} BTNode;

int CalcGreaterNodes(BTNode* bt, char x) {
    return bt == nullptr ? 0 : (bt->data > x ? (cout << bt->data, 1) : 0) + CalcGreaterNodes(bt->lchild, x) + CalcGreaterNodes(bt->rchild, x);
}

// 在此处补充你的代码
void CreateBTree(BTNode*& bt, char* str)    //由括号表示串创建二叉链
{
    BTNode* St[MaxSize], * p = NULL;
    int top = -1, k, j = 0;
    char ch;
    bt = NULL;
    ch = str[j];
    while (ch != '\0') {
        switch (ch) {
            case '(':top++; St[top] = p; k = 1; break;
            case ')':top--; break;
            case ',':k = 2; break;
            default:p = new BTNode();
                p->data = ch; p->lchild = p->rchild = NULL;
                if (bt == NULL)
                    bt = p;
                else {
                    switch (k) {
                        case 1:St[top]->lchild = p; break;
                        case 2:St[top]->rchild = p; break;
                    }
                }
        }
        j++;
        ch = str[j];
    }
}
void DestroyBTree(BTNode*& bt)        //销毁二叉树
{
    if (bt != NULL) {
        DestroyBTree(bt->lchild);
        DestroyBTree(bt->rchild);
        delete bt;
    }
}
int main() {
    char btree[MaxSize];
    cin >> btree;
    char x;
    cin >> x;
    BTNode* bt;
    CreateBTree(bt, btree);
    int n = CalcGreaterNodes(bt, x);
    cout << n << endl;
    DestroyBTree(bt);
    return 0;
}