二叉树结构

struct TreeNode{
    int val;
    TreeNode* left= nullptr;
    TreeNode* right= nullptr;
    explicit TreeNode(int v):val(v){}
};

层序生成二叉树

给定一个数num，生成层序为从0到num的二叉树

TreeNode* TreeInit(int num){
    auto new_root = new TreeNode(0);
    queue<TreeNode*> q;   //辅助队列
    int i=1;
    auto p=new_root;
    bool flag = false;
    while (i<=num){
        if (!flag){
            p->left = new TreeNode(i);
            q.push(p->left);
            flag = true;
            i++;
            continue;
        }
        else {
            p->right = new TreeNode(i);
            q.push(p->right);
            p=q.front();
            q.pop();
            flag = false;
            i++;
            continue;
        }
    }
    return new_root;
}

前中后序遍历二叉树

void PreTraverse(TreeNode* root){
    if (root== nullptr){
        return;
    }
    cout<<root->val<<' ';
    PreTraverse(root->left);
    PreTraverse(root->right);
}

void MidTraverse(TreeNode* root){
    if (root== nullptr){
        return;
    }
    MidTraverse(root->left);
    cout<<root->val<<' ';
    MidTraverse(root->right);
}

void LasTraverse(TreeNode* root){
    if (root== nullptr){
        return;
    }
    LasTraverse(root->left);
    LasTraverse(root->right);
    cout<<root->val<<' ';
}

层次遍历

void LevelTraverse(TreeNode* root){
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()){
        if (q.front()->left!= nullptr){
            q.push(q.front()->left);
        }
        if (q.front()->right!= nullptr){
            q.push(q.front()->right);
        }
        cout<<q.front()->val<<' ';
        q.pop();
    }
}