用c++完成树的存储与遍历 1.初始化二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.销毁二叉树 (2) 二叉树的复原 1.由前序、中序序列确定复原二叉树 2.由中序、后序序列确定复原二叉树

树的存储与遍历：

1.初始化二叉树

#include <iostream>
using namespace std;

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

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

2.先序遍历二叉树

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

3.中序遍历二叉树

void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

4.后序遍历二叉树

void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

5.销毁二叉树

void destroyTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    destroyTree(root->left);
    destroyTree(root->right);
    delete root;
}

二叉树的复原：

1.由前序、中序序列确定复原二叉树

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return NULL;
    }
    int rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    vector<int>::iterator it = find(inorder.begin(), inorder.end(), rootVal);
    int leftSize = it - inorder.begin();
    vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftSize);
    vector<int> leftInorder(inorder.begin(), it);
    vector<int> rightPreorder(preorder.begin() + 1 + leftSize, preorder.end());
    vector<int> rightInorder(it + 1, inorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

2.由中序、后序序列确定复原二叉树

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.empty() || postorder.empty()) {
        return NULL;
    }
    int rootVal = postorder.back();
    TreeNode* root = new TreeNode(rootVal);
    vector<int>::iterator it = find(inorder.begin(), inorder.end(), rootVal);
    int leftSize = it - inorder.begin();
    vector<int> leftInorder(inorder.begin(), it);
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftSize);
    vector<int> rightInorder(it + 1, inorder.end());
    vector<int> rightPostorder(postorder.begin() + leftSize, postorder.end() - 1);
    root->left = buildTree(leftInorder, leftPostorder);
    root->right = buildTree(rightInorder, rightPostorder);
    return root;
}