机试第10章

前序遍历序列建二叉树

string str;
int pos = 0;

TreeNode *build(string str, int &pos)
{
    char c = str[pos++];
    if (c == '#')
        return nullptr;
    TreeNode *root = new TreeNode(c);
    root->lchild = build(str, pos);
    root->rchild = build(str, pos);
    return root;
}

根据前序序列和中序序列确定二叉树

TreeNode *build(int l1, int r1, int l2, int r2, string &pre, string &in)
{
    if (l1 > r1)
        return nullptr;
    TreeNode *root = new TreeNode(pre[l1]);
    int pos = in.find(pre[l1]);
    root->lchild = build(l1 + 1, l1 + pos + 1, l2, pos - 1, pre, in);
    root->rchild = build(l1 + pos + 2, r1, pos + 1, r2, pre, in);
    return root;
}

TreeNode *make(string &pre, string &in)
{
    return build(0, pre.size() - 1, 0, in.size() - 1, pre, in);
}

二叉排序树建树

TreeNode *insert(TreeNode *root, int val, int father)
{
    if (!root)
    {
        root = new TreeNode(val);
        cout << father << " ";
    }
    else if (val < root->val)
        root->lchild = insert(root->lchild, val, root->val);
    else
        root->rchild = insert(root->rchild, val, root->val);
    return root;
}

判断两棵树是否相同

bool isEqual(TreeNode *x, TreeNode *y)
{
    if (x == nullptr && y == nullptr)
        return true;
    if ((x == nullptr && y != nullptr) || (x != nullptr && y == nullptr))
        return false;
    if (x->val != y->val)
        return false;
    return isEqual(x->lchild, y->lchild) && isEqual(x->rchild, y->rchild);
}

哈夫曼树最小带权路径长度和

priority_queue<int, vector<int>, greater<int>> q; // 小根堆

int res = 0;
while (q.size() > 1)
{
    int a = q.top();
    q.pop();
    int b = q.top();
    q.pop();
    res += a + b;
    q.push(a + b);
}

哈夫曼树建树及哈夫曼编码

struct cmp
{
    bool operator()(TreeNode *lhs, TreeNode *rhs)
    {
        return lhs->val > rhs->val;
    }
};

string tmp;
vector<string> res;
unordered_map<TreeNode *, int> mp; // 给每个节点赋序号
priority_queue<TreeNode *, vector<TreeNode *>, cmp> q;
res.resize(q.size());

void build() // 建树
{
    while (q.size() > 1)
    {
        TreeNode *a = q.top();
        q.pop();
        TreeNode *b = q.top();
        q.pop();
        TreeNode *root = new TreeNode(a->val + b->val);
        root->lchild = a, root->rchild = b;
        q.push(root);
    }
}

void solve(TreeNode *root) // 编码
{
    if (!root)
        return;
    if (!root->lchild && !root->rchild)
    {
        res[mp[root]] = tmp;
        return;
    }
    tmp += "0";
    solve(root->lchild);
    tmp.pop_back();
    tmp += "1";
    solve(root->rchild);
    tmp.pop_back();
}