C++实现二叉树构建：顺序数组、前序数组和后序数组详解

C++实现二叉树构建：顺序数组、前序数组和后序数组详解

在C++编程中，二叉树是一种重要的数据结构，掌握其构建方法对于算法设计和开发至关重要。本文将详细介绍如何通过数组快速构建二叉树，包括顺序数组、前序数组和后序数组的构建方法。

完全二叉树的构建

在前面的学习中，我们知道了完全二叉树有一个非常 nice 的性质，它每个结点的左孩子在数组中的位置等于 2x ，右孩子等于 2x+1 。通过这个性质，我们可以快速的构建起一个二叉树。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left_node;
    Node *right_node;
};
int n;    //表示数组长度
//递归法构建二叉树
Node *creatTree(vector<int> nums, int index) {
    //判断是否为空
    if (nums[index] == '#')
        return NULL;
    //创建新结点
    Node *root = new Node;
    root->data = nums[index];
    //设置左右指针
    if (index * 2 <= n)
        root->left_node = creatTree(nums, index * 2);    //找到左孩子
    else
        root->left_node = NULL;
    if (index * 2 + 1 <= n)
        root->right_node = creatTree(nums, index * 2 + 1);    //找到右孩子
    else
        root->right_node = NULL;
    return root;
}
//非递归构建二叉树（利用栈）—— 前序遍历
void stackCreatTree(vector<int> nums) {
    int n = nums.size();
    stack<int> s;
    int index;    //记录遍历到第几个元素
    s.push(1);    //推入根结点，开始遍历
    while (!s.empty()) {
        index = s.top();
        s.pop();
        cout << nums[index] << " ";
        //先推入右孩子
        if (index * 2 + 1 < n && nums[index * 2 + 1] != '#')
            s.push(index * 2 + 1);
        //再推入左孩子，因为是栈结构，先进后出，而且前序遍历需要优先访问所有左子树，故只有一直放在栈顶才能先访问
        if (index * 2 < n && nums[index * 2] != '#')
            s.push(index * 2);
    }
    cout << endl;
}
//前序遍历
void PreOrderTraverse(Node *root) {
    if (root) {
        cout << root->data << " ";
        PreOrderTraverse(root->left_node);
        PreOrderTraverse(root->right_node);
    }
}
int main() {
    vector<int> nums = { '#', 1, 2, 3, 4, 5, '#', 6, '#', '#', 7, 8 };    //'#'指向空，并且从下标1开始存数据
    n = nums.size();
    Node *root = creatTree(nums, 1);
    PreOrderTraverse(root);
    cout << endl;
    stackCreatTree(nums);
    return 0;
}  

根据前序和后序数组构建二叉树

除了给定一个顺序存储的数组外，还可能会给定前序遍历的结果，让你构建出二叉树。这里的操作和上面比较类似，但区别是我们获取结点的左右孩子的方式变了，上面我们是根据完全二叉树的性质。

（1）这里我们可以根据前序遍历的性质，也就是遍历结果遵循 根结点 | 左子树 | 右子树 的结果。所以，我们直接可以用一个全局变量下标来记录我们遍历的位置，从头往后遍历，每次都加 1 ，这样就可以连起来了。

（2）同样，后序遍历结果是遵循 左子树 | 右子树 | 根结点 的结果。所以，我们可以从最后一个元素开始往前遍历，每次都减 1 ，同样可以构建出来。

这里我们不用去判断下标是否超过数组长度，因为给定的数组是一定满足要求的即左子树右子树是否为空直接看'#'就可以。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left_node;
    Node *right_node;
};
int n;    //表示数组长度
int index;    //表示遍历到的下标
//前序数组创建二叉树
Node *prevCreatTree(vector<int> nums) {
    //判断是否为空
    if (nums[index] == '#') {
        index++;
        return NULL;
    }
    //创建结点
    Node *root = new Node;
    root->data = nums[index++];
    root->left_node = prevCreatTree(nums);
    root->right_node = prevCreatTree(nums);
    return root;
}
//后序数组创建二叉树
int cnt;
Node *backCreatTree(vector<int> nums) {
    if (nums[cnt] == '#') {
        cnt--;
        return NULL;
    }
    Node *root = new Node;
    root->data = nums[cnt--];
    root->right_node = backCreatTree(nums);
    root->left_node = backCreatTree(nums);
    return root;
}
//中序遍历
void InOrderTraverse(Node *root) {
    if (root) {
        InOrderTraverse(root->left_node);
        cout << root->data << " ";
        InOrderTraverse(root->right_node);
    }
}
int main() {
    //'#'指向空
    vector<int> nums1 = { 1, 2, 3, '#', '#', 4, '#', '#', 5, '#', '#' };
    vector<int> nums2 = {'#', '#', 3, '#', '#', 4, 2, '#', '#', 5, 1};
    index = 0;    //初始化下标
    Node *prev_root = prevCreatTree(nums1);
    InOrderTraverse(prev_root);
    cout << endl;
    cnt = nums2.size() - 1;
    Node *back_root = backCreatTree(nums2);
    InOrderTraverse(back_root);
    return 0;
}