算法原理与实践（二叉树）

#include <iostream>
#include <string>
#include <queue>
#include <vector>

using namespace std;

const char INVALID = ‘#‘;

struct node {
    node() : left(nullptr), right(nullptr) {};
    char val;
    struct node* left;
    struct node* right;
};

class BinaryTree {
public:
    BinaryTree(const string& initial) : root(nullptr)
    {
        string::const_iterator it = initial.cbegin();
        while (it != initial.cend())
            this->q.push(*it++);
    }

    void createRecursion()
    {
        this->createNodeRecursion(this->root);
    }

    void visitRecursion()
    {
        this->visitNodeRecursion(this->root);
    }

    ~BinaryTree()
    {
        //习惯时 
        for (size_t i = this->v.size(); i != 0; i--)
            delete this->v[i - 1];
    }

private:
    void createNodeRecursion(struct node*& p)
    {
        if (this->q.front() == INVALID)
        {
            p = nullptr;
            this->q.pop();
            return;
        }
        else
        {
            p = this->applyNode(); //申请节点
            p->val = q.front();
            this->q.pop();

            this->createNodeRecursion(p->left);
            this->createNodeRecursion(p->right);
        }
    }

    void visitNodeRecursion(const struct node* p)
    {
        if (p == nullptr)
        {
            this->notify(‘#‘);
            return;
        }
        else
        {
            this->notify(p->val);
            this->visitNodeRecursion(p->left);
            this->visitNodeRecursion(p->right);
        }
    }

    void notify(char c)
    {
        cout << c << " ";
    }

    /* 向内存池申请一块树节点 */
    struct node* applyNode() {
        struct node* p = new node();
        v.push_back(p);
        return p;
    }
    
    struct node* root;
    queue<char> q;
    vector<struct node*> v; //内存池
};

int main()
{
    string s = "31#2##568###7##";

    BinaryTree bt(s);
    bt.createRecursion();
    bt.visitRecursion();

    return 0;
}