树

树的遍历

树的递归遍历

//树的存储结构
Tree Node
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode (int x):val(x),left(NULL),right(NULL){};
};

//中序遍历
void order(TreeNode *root)
{
    if(!root) return;
    inorder(root->left);
    cout<<root<<' ';
    inorder(root->right);
}

//前序遍历
void preorder(TreeNode *root)
{
    if(!root) return;
    cout<<root<<' ';
    inorder(root->left);
    inorder(root->right);
}

//后序遍历
void postorder(TreeNode *root)
{
    if(!root) return;
    inorder(root->left);
    inorder(root->right);
    cout<<root<<' ';
}

非递归遍历

//非递归中序遍历:
void inorder2(TreeNode* root)
{
    stack<TreeNode*> stk;
    TreeNode* curr = root;

    while(curr || !stk.empty())
    {
        // 把当前节点的左子节点全部压入栈
        while(curr)
        {
            stk.push(curr);
            curr = curr->left;
        }

        // 从栈中弹出一个节点计算
        curr = stk.top();
        stk.pop();

        // 输出节点
        cout << curr->val << " ";

        // 让当前节点指向右子节点
        curr = curr->right;
    }
}

二叉排序树

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 1e8;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;

void insert(TreeNode* &root, int x)
{
    if (!root) root = new TreeNode(x);
    else if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}

void remove(TreeNode* &root, int x)
{
    if (!root) return;
    if (x < root->val) remove(root->left, x);
    else if (x > root->val) remove(root->right, x);
    else
    {
        if (!root->left && !root->right) root = NULL;
        else if (!root->left) root = root->right;
        else if (!root->right) root = root->left;
        else
        {
            auto p = root->left;
            while (p->right) p = p->right;
            root->val = p->val;
            remove(root->left, p->val);
        }
    }
}

int get_pre(TreeNode* root, int x)
{
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    return max(root->val, get_pre(root->right, x));
}

int get_suc(TreeNode* root, int x)
{
    if (!root) return INF;
    if (root->val <= x) return get_suc(root->right, x);
    return min(root->val, get_suc(root->left, x));
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int t, x;
        cin >> t >> x;
        if (t == 1) insert(root, x);
        else if (t == 2) remove(root, x);
        else if (t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suc(root, x) << endl;
    }

    return 0;
}

带权路径长度

//wpl
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int dfs(TreeNode * root,int depth){
        if(!root) return 0;
        if(!root->left && !root->right) return root->val *depth;
        return dfs(root->left,depth + 1) + dfs(root-> right, depth + 1);
    }

    int pathSum(TreeNode* root) {
        return dfs(root, 0);
    }
};

应用

表达式树

//o(n^2)
struct TreeNode {
    string val；
    TreeNode *left;
    TreeNode *right;
};
class Solution {
public:
    string dfs(TreeNode* root)
    {
        if(!root) return "";
        if(!root ->left && !root->right) return root->val;
        return '(' + dfs(root->left) + root->val +dfs(root->right) + ')';
    }

    string expressionTree(TreeNode* root) {
        return dfs(root ->left) +root->val +dfs(root->right);
    }
};

//o(n)
class Solution {
public:
    string ans;

    void dfs(TreeNode *root){
        if(!root) return;
        if(!root->left && !root->right) ans += root->val;
        else
        {
            ans += '(';
            dfs(root->left);
            ans += root->val;
            dfs(root->right);
            ans += ')';            
        }
    }
    string expressionTree(TreeNode *root){
        dfs(root->left), ans += root->val,dfs(root->right);
        return ans;
    }
};

哈夫曼树_堆

//输入两行，第一行是总堆数，第二行是每个堆的元素数目
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int main()//堆实现
{
    int n;
    scanf("%d",&n);
    priority_queue <int, vector<int>, greater<int>> heap;

    // priority_queue 又称为优先队列，其底层是用堆来进行实现的。
    //在优先队列中，队首元素一定是当前队列中优先级最高的那一个。

    // priority_queue<int> q;

    // priority_queue<int,vector<int>,less<int>> q;
    // 多出了两个参数：一个是 vector<int>，另一个是 less<int>。

    //其中 vector<int>（第二个参数）填写的是来承载底层数据结构堆（heap）的容器
    //如果第一个参数是double 或 char 型，则只需要填写 vector<double> 或 vector<char>；

    //而第三个参数 less<int> 则是对第一个参数的比较类，
    //less<int> 表示数字大的优先级越大，而 greater<int> 表示数字小的优先级越大。

    //因此，如果想让优先队列总是把最小的元素放在队首，
    //只需进行如下定义：priority_queue<int,vector<int>,greater<int>>q;
    while(n--)
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }
    int res = 0;

    while(heap.size() > 1)
    {
        auto a = heap.top();
        heap.pop();
        auto b = heap.top();
        heap.pop();
        res += a + b;
        heap.push(a+b);
    }

    printf("%d",res);
    return 0;
}