нерекурсивное построение идеального бинарного дерева из обхода его по порядку - PullRequest
Новая
       31

нерекурсивное построение идеального бинарного дерева из обхода его по порядку

0 голосов
/ 09 сентября 2018

Учитывая обход INORDER совершенного двоичного дерева, сгенерируйте соответствующее двоичное дерево. Кроме того, итеративным способом получите обход INORDER, PREORDER, POSTORDER и LEVELORDER сгенерированного дерева. Мне не ясно, что означает идеальное бинарное дерево, здесь реализация приведенного выше кода, но она не делает именно то, что говорит вышеупомянутая проблема 

using namespace std;


// Node structure
struct Node
{
    int key;
    struct Node *left, *right;
};

// function to create a new tree Node
struct Node *newNode(int item)
{
    struct Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

//  function to do preorder traversal of BST
void preorder(Node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}

vector<Node *> getTrees(int arr[], int start, int end)
{
    vector<Node *> trees;

    if (start > end)
    {
        trees.push_back(NULL);
        return trees;
    }

    for (int i = start; i <= end; i++)
    {
        vector<Node *> ltrees = getTrees(arr, start, i-1);

        vector<Node *> rtrees = getTrees(arr, i+1, end);

        for (int j = 0; j < ltrees.size(); j++)
        {
            for (int k = 0; k < rtrees.size(); k++)
            {
                Node * node = newNode(arr[i]);

                node->left = ltrees[j];

                node->right = rtrees[k];

                trees.push_back(node);
            }
        }
    }
    return trees;
}

int main()
{

    int choice=1;
    int i=0;int n;
    int in[100];
    cout <<"Enter the inorder traversal"<<endl;
    do{
        cout <<"enter number "<<endl;
        cin>>in[i];
        i++;
        cout <<"Enter choice 1 to enter 0 to exit"<<endl;
        cin >> choice;
        }
    while (choice==1);
    n=i-1; //to know how many elements were entered we do n=i but in while loop i would have increased by 1 so n=i-1
    vector<Node *> trees = getTrees(in, 0, n-1);

    cout << "Preorder traversals of different "
         << "possible Binary Trees are \n";
    for (int i = 0; i < trees.size(); i++)
    {
        preorder(trees[i]);
        printf("\n");
    }
    return 0;
}

Любой алгоритм, который может решить эту проблему, потому что реализация неверна, и я не могу думать иначе, как эта реализация.

...