数据结构-构建二叉树

用先序序列和中序序列构建二叉树，采用二叉链表存储。编写递归算法，交换二叉树的左右子树，
输出新二叉树按先序遍历得到的结果。

提交格式：实现void solve(int n, int *preOrder, int *inOrder, int *outOrder)函数。
函数参数为序列长度n、先序序列preOrder、中序序列inOrder和输出序列outOrder。1<=n<=1000000，树的深度<=2000。
请不要printf输出任何内容。

输入样例1：
n=5,preOrder={1,2,3,4,5},inOrder={3,2,4,1,5}
输出样例1：
outOrder={1,5,2,4,3}

可以使用以下代码来实现递归交换二叉树左右子树的算法：

#include <iostream>
#include <vector>

using namespace std;

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

// 通过先序遍历和中序遍历构建二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
  if (preorder.empty()) return NULL;

  int root_val = preorder[0];
  TreeNode* root = new TreeNode(root_val);

  int k = 0;
  // 找到根节点在中序遍历中的位置
  while (inorder[k] != root_val) ++k;

  vector<int> left_preorder(preorder.begin() + 1, preorder.begin() + 1 + k);
  vector<int> left_inorder(inorder.begin(), inorder.begin() + k);
  root->left = buildTree(left_preorder, left_inorder);

  vector<int> right_preorder(preorder.begin() + 1 + k, preorder.end());
  vector<int> right_inorder(inorder.begin() + k + 1, inorder.end());
  root->right = buildTree(right_preorder, right_inorder);

  return root;
}

// 递归交换二叉树的左右子树
void swapSubtrees(TreeNode* root) {
  if (root == NULL) return;
  swap(root->left, root->right);
  swapSubtrees(root->left);
  swapSubtrees(root->right);
}

// 先序遍历二叉树，将遍历结果存入数组中
void preOrderTraverse(TreeNode* root, vector<int>& outOrder) {
  if (root == NULL) return;
  outOrder.push_back(root->val);
  preOrderTraverse(root->left, outOrder);
  preOrderTraverse(root->right, outOrder);
}

void solve(int n, int* preOrder, int* inOrder, int* outOrder) {
  // 将先序遍历和中序遍历的数组转为 vector
  vector<int> preorder(preOrder, preOrder + n);
  vector<int> inorder(inOrder, inOrder + n);

  // 通过先序遍历和中序遍历构建二叉树
TreeNode* root = buildTree(preorder, inorder);
// 递归交换二叉树的左右子树
swapSubtrees(root);
// 先序遍历二叉树，将遍历结果存入数组中
vector<int> outorder;
preOrderTraverse(root, outorder);

// 将 vector 转为数组
copy(outorder.begin(), outorder.end(), outOrder);
}

在函数 solve 中，首先将先序遍历和中序遍历的数组转为 vector，然后调用函数 buildTree 来构建二叉树。然后调用函数 swapSubtrees 来递归交换二叉树的左右子树，最后调用函数 preOrderTraverse 对二叉树进行先序遍历，将遍历结果存入数组中。

#include <iostream>
using namespace std;
typedef struct BiNode
{
    char date; //二叉链表的定义
    struct BiNode *lchild, *rchild;
} BiTNode, *BiTree;

//用先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T) //&引用
{
    //按照先序次序输入二叉树中节点的值（一个字符），创建二叉链表表示的二叉树T；
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BiTNode;         // 分配空间
        T->date = ch;            // 生成根节点
        CreateBiTree(T->lchild); //递归创建左子数
        CreateBiTree(T->rchild); //递归创建右子树
    }
}
//中序遍历二叉树T的递归算法 左根右，如果想搞清楚无比要懂得如何递归且根据图来画一画。
void InOrderTraverse(BiTree T)
{
    if (T)
    {
        InOrderTraverse(T->lchild);
        cout << T->date;
        InOrderTraverse(T->rchild);
    }
}
int main()
{
    BiTree tree;
    cout << "请输入二叉链表的序列: \n";
    CreateBiTree(tree);
    cout << "遍历结果为：\n";
    InOrderTraverse(tree);

}

#include<iostream>

using namespace std;
#define OK 1
#define ERROR 0
#define FALSE -1
#define OVERFLOW -2

typedef char TElemType;
typedef int Status;

typedef struct BiTNode {
    TElemType data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;


//初始化
Status InitBiTree(BiTree T) {
    if (!(T = new BiTNode)) return ERROR;
    T->lchild = NULL;
    T->rchild = NULL;
    return OK;
}

Status DestoryBiTree(BiTree& T) {
    if (!T) return FALSE;
    else {
        if (T->lchild != NULL)
            DestoryBiTree(T->lchild);
        if (T->rchild != NULL)
            DestoryBiTree(T->rchild);

        delete T;
        return OK;
    }
}


BiTree Root(BiTree T) {
    if (T == NULL) return NULL;
    return T;
}


Status ClearBiTree(BiTree T) {
    BiTNode* p;
    p = T;
    if (p) {
        DestoryBiTree(p);
        T->lchild = NULL;
        T->rchild = NULL;
        return OK;
    }
}

//用前序遍历的递归方式实现深度优先搜索
void PreOrderTraverse(BiTree T) {
    //T为树根的指针
    //如果T非空
    if (T) {
        //输出T结点的值
        cout << T->data << " ";
        //遍历左子树
        PreOrderTraverse(T->lchild);
        //遍历右子树
        PreOrderTraverse(T->rchild);
    }
    else return;
}

//创建二叉树
Status CreatBiTree(BiTree& T) {

    char ch;
    cin >> ch;
    if (ch == '#') T = NULL;//#代表二叉树为空树
    else {
        if (!(T = new BiTNode))
            exit(OVERFLOW);
        T->data = ch;//生成根节点
        CreatBiTree(T->lchild);//递归创建左子树
        CreatBiTree(T->rchild);//递归创建右子树
    }
    return OK;
}



int main() {
    BiTree root = NULL;
    InitBiTree(root);
    cout << "请按先序次序输入二叉树，#表示空树" << endl;
    CreatBiTree(root);
    cout << "二叉树深度优先搜索的结果为" << endl;
    PreOrderTraverse(root);

    return 0;
}

#include <stdio.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *buildTree(int n, int *preOrder, int *inOrder, int *outOrder) {
    // 判断输入序列是否合法
    if (n <= 0 || preOrder == NULL || inOrder == NULL || outOrder == NULL) {
        return NULL;
    }

    // 在中序序列中找到根节点的位置
    int rootIndex = 0;
    while (rootIndex < n && inOrder[rootIndex] != preOrder[0]) {
        rootIndex++;
    }

    // 创建根节点
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = preOrder[0];
    root->left = NULL;
    root->right = NULL;

    // 递归构建左子树
    int leftSubtreeSize = rootIndex;
    int *leftPreOrder = preOrder + 1;
    int *leftInOrder = inOrder;
    int *leftOutOrder = outOrder;
    root->left = buildTree(leftSubtreeSize, leftPreOrder, leftInOrder, leftOutOrder);

    // 递归构建右子树
    int rightSubtreeSize = n - 1 - rootIndex;
    int *rightPreOrder = preOrder + 1 + rootIndex;
    int *rightInOrder = inOrder + 1 + rootIndex;
    int *rightOutOrder = outOrder + leftSubtreeSize + 1;
    root->right = buildTree(rightSubtreeSize, rightPreOrder, rightInOrder, rightOutOrder);

    return root;
}

int main(void) {
    int n = 5;
    int preOrder[5] = {1, 2, 3, 4, 5};
    int inOrder[5] = {3, 2, 4, 1, 5};
    int outOrder[5];

    TreeNode *root = buildTree(n, preOrder, inOrder, outOrder);

    return 0;
}

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7592090
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：数据结构 - 搜索二叉树

这道题可以使用动态规划来解决。

首先，我们可以使用一个二维数组 $dp[i][j]$ 表示在计算矩阵 $A_i \cdots A_j$ 连乘积的最小乘次数。这个数组的每一个元素都可以由更小范围内的矩阵连乘转移而来。具体地，我们可以枚举 $k$，使得 $i \leq k < j$，然后计算出 $dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]p[k]p[j])$。

除了计算最小乘次数之外，我们还需要记录下来矩阵连乘的次序。我们可以使用一个二维数组 $s[i][j]$ 表示在计算矩阵 $A_i \cdots A_j$ 连乘积时，$dp[i][j]$ 这个值是由哪个矩阵转移而来的。这样，我们就可以通过 $s$ 数组得到矩阵连乘的次序。

最后，我们可以通过递归的方式来输出矩阵连乘的次序。具体来说，我们可以写一个函数，输入为 $i$ 和 $j$，然后判断 $i=j$ 的情况，输出 $i$。否则，我们输出 $-1$，然后调用递归函数来处理 $i$ 到 $s[i][j]$ 之间的矩阵，然后再输出 $s[i][j]+1$

 
#include<iostream>
 
using namespace std;
#define OK 1
#define ERROR 0
#define FALSE -1
#define OVERFLOW -2
 
typedef char TElemType;
typedef int Status;
 
typedef struct BiTNode {
    TElemType data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
 
//初始化
Status InitBiTree(BiTree T) {
    if (!(T = new BiTNode)) return ERROR;
    T->lchild = NULL;
    T->rchild = NULL;
    return OK;
}
 
Status DestoryBiTree(BiTree& T) {
    if (!T) return FALSE;
    else {
        if (T->lchild != NULL)
            DestoryBiTree(T->lchild);
        if (T->rchild != NULL)
            DestoryBiTree(T->rchild);
 
        delete T;
        return OK;
    }
}
 
 
BiTree Root(BiTree T) {
    if (T == NULL) return NULL;
    return T;
}
 
 
Status ClearBiTree(BiTree T) {
    BiTNode* p;
    p = T;
    if (p) {
        DestoryBiTree(p);
        T->lchild = NULL;
        T->rchild = NULL;
        return OK;
    }
}
 
//用前序遍历的递归方式实现深度优先搜索
void PreOrderTraverse(BiTree T) {
    //T为树根的指针
    //如果T非空
    if (T) {
        //输出T结点的值
        cout << T->data << " ";
        //遍历左子树
        PreOrderTraverse(T->lchild);
        //遍历右子树
        PreOrderTraverse(T->rchild);
    }
    else return;
}
 
//创建二叉树
Status CreatBiTree(BiTree& T) {
 
    char ch;
    cin >> ch;
    if (ch == '#') T = NULL;//#代表二叉树为空树
    else {
        if (!(T = new BiTNode))
            exit(OVERFLOW);
        T->data = ch;//生成根节点
        CreatBiTree(T->lchild);//递归创建左子树
        CreatBiTree(T->rchild);//递归创建右子树
    }
    return OK;
}
 
 
 
int main() {
    BiTree root = NULL;
    InitBiTree(root);
    cout << "请按先序次序输入二叉树，#表示空树" << endl;
    CreatBiTree(root);
    cout << "二叉树深度优先搜索的结果为" << endl;
    PreOrderTraverse(root);
 
    return 0;
}

#include <stdio.h>
#define ElemType char
//节点声明，数据域、左孩子指针、右孩子指针
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉树
BiTree CreateBiTree(){
    char ch;
    BiTree T;
    scanf("%c",&ch);
    if(ch=='#')T=NULL;
    else{
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = ch;
        T->lchild = CreateBiTree();
        T->rchild = CreateBiTree();
    }
    return T;//返回根节点
}