Construct a binary tree whose following traversal are given Inorder X.,y,z.a,p,q,r preorder a,y,x,z,q,p,r Data structure using c++

 Open sidebar

Construct Binary Tree.

Construct a binary tree whose following traversal are given

     Inorder X.,y,z.a,p,q,r

     preorder a,y,x,z,q,p,r

Data structure using c++

Here's an example of how you can construct a binary tree in C++ given the inorder and preorder traversals:

cpp

Copy code

#include <iostream>

using namespace std;

// Definition of a binary tree node

struct TreeNode {

    char val;

    TreeNode* left;

    TreeNode* right;

    TreeNode(char value) {

        val = value;

        left = nullptr;

        right = nullptr;

    }

};

int findIndex(char inorder[], int start, int end, char target) {

    for (int i = start; i <= end; i++) {

        if (inorder[i] == target)

            return i;

    }

    return -1;

}

TreeNode* buildTreeHelper(char inorder[], char preorder[], int inStart, int inEnd, int& preIndex) {

    if (inStart > inEnd)

        return nullptr;

    TreeNode* newNode = new TreeNode(preorder[preIndex++]);

    if (inStart == inEnd)

        return newNode;

    int inIndex = findIndex(inorder, inStart, inEnd, newNode->val);

    newNode->left = buildTreeHelper(inorder, preorder, inStart, inIndex - 1, preIndex);

    newNode->right = buildTreeHelper(inorder, preorder, inIndex + 1, inEnd, preIndex);

    return newNode;

}

TreeNode* buildTree(char inorder[], char preorder[], int size) {

    int preIndex = 0;

    return buildTreeHelper(inorder, preorder, 0, size - 1, preIndex);

}

void printInorder(TreeNode* root) {

    if (root == nullptr)

        return;

    printInorder(root->left);

    cout << root->val << " ";

    printInorder(root->right);

}

int main() {

    char inorder[] = { 'X', '.', 'y', ',', 'z', '.', 'a', ',', 'p', ',', 'q', ',', 'r' };

    char preorder[] = { 'a', ',', 'y', ',', 'x', '.', 'z', ',', 'q', ',', 'p', ',', 'r' };

    int size = sizeof(inorder) / sizeof(inorder[0]);

    TreeNode* root = buildTree(inorder, preorder, size);

    cout << "Inorder traversal: ";

    printInorder(root);

    return 0;

}

This code constructs a binary tree based on the given inorder and preorder traversals. It defines a TreeNode structure and two functions buildTree and buildTreeHelper to build the tree recursively. The findIndex function is used to find the index of a given value in the inorder array. The printInorder function is used to print the inorder traversal of the constructed tree.

In the main function, we provide the example inorder and preorder traversals and call the buildTree function to construct the binary tree. Then, we print the inorder traversal to verify the correctness of the construction.

Please note that this code assumes the provided traversals are valid and represent a binary tree.