Построение бинарного дерева из заданного предварительного и последующего порядка с использованием рекурсии

Я делаю бинарное дерево в форме, заданной до и после заказа.

предварительный заказ: «vwbcyznamlp»

Пост-заказ: «cbznywmplav»

ЛОГИКА ДЛЯ ЭТОЙ ЦЕЛИ

V W B C Y Z N A M L P
C B Z N Y W M P L A V

Во-первых, обратите внимание, что корень — это V, потому что он первый в предварительном заказе и последний в почтовом заказе:

V W B C Y Z N A M L P
C B Z N Y W M P L A V

Затем посмотрите на W и A, они, соответственно, они первый левый потомок и последний правый потомок корня. A в предзаказе обозначает место, где переход переходит от левого поддерева корня к правому поддереву корня. W в почтовом порядке отмечает то же место. Обратите внимание, что когда вы разделяете обходы, A и W являются смежными позициями:

V W B C Y Z N    A M L P
C B Z N Y W    M P L A V

Теперь вам осталось решить ту же задачу для последовательностей:

W B C Y Z N
C B Z N Y W

а также

A M L P
M P L A

Например, следующим шагом для первой последовательности будет:

W B C    Y Z N
C B    Z N Y W

Я делаю дерево с помощью рекурсии, но некоторые условия в рекурсии я не узнал. Поэтому, когда я пересекаю это дерево через преодер, тогда ответ был неправильным.

После создания дерева с помощью рекурсии ответ был

предварительный заказ: «vwbccyznaml»

Код, который я сделал, здесь

Сначала я сделал Tree Struct

  #include <iostream>
#include <string>
#include <stack>
using namespace std;
struct TreeNode
{
public:
string enteredData;
struct TreeNode *left;
struct TreeNode *right;
struct TreeNode* newNode(string data)
{
struct TreeNode* temp = new TreeNode();
temp->enteredData = data;
temp->left = temp->right = NULL;
return temp;
}
};
struct TreeNode* Buildingtree(string preorder, string postorder);

Дополнительные функции

//for returning tree
struct TreeNode *constructTree(string preorder, string postorder)
{
int preIndex = 0;
return Buildingtree(preorder, postorder);
}//for pre-order traversal
void printPreorder(struct TreeNode* node)
{
if (node == NULL)
return;
cout << node->enteredData << " ";
printPreorder(node->left);
printPreorder(node->right);
}//for building tree from given preorder and postorder
struct TreeNode* Buildingtree(string preorder, string postorder)
{
string newPreoderForFunction = "";
string newPostoderForFunction = "";
struct TreeNode* root = new TreeNode();
string rightpreorder;
string rightpostorder;
static stack<string> u;
int indexForPreOder = 1;
int indexForPostOrder = postorder.length() - 2;
if (indexForPostOrder <= -1)
{
string g;
if (preorder != "")
g.assign(1, preorder[0]);
else
g.assign(1, postorder[0]);
root = root->newNode(g);
return root;
}
else
{
string findingCharFromPreorder;
findingCharFromPreorder.assign(1, preorder[indexForPreOder]);
string findingCharFromPostorder;
findingCharFromPostorder.assign(1, postorder[indexForPostOrder]);
size_t found;
string h = "";
if (preorder != "")
h.assign(1, preorder[0]);
else if (postorder != "")
h.assign(1, postorder[0]);
root = root->newNode(h);
if ((found = preorder.find(findingCharFromPostorder)) != string::npos)
{
newPreoderForFunction = preorder.substr(1, found - 1);
rightpreorder = preorder.substr(found, preorder.length() - 1);
u.push(rightpreorder);
}
if ((found = postorder.find(findingCharFromPreorder)) != string::npos)
{

newPostoderForFunction = postorder.substr(0, found + 1);

rightpostorder = postorder.substr(found + 1, indexForPostOrder);

if (rightpostorder.length() > 1)
rightpostorder.erase(rightpostorder.length() - 1);
u.push(rightpostorder);

}
}
root->left = Buildingtree(newPreoderForFunction, newPostoderForFunction);
string a;
string b;
a = u.top();
u.pop();
b = u.top();
u.pop();
root->right = Buildingtree(b, a);
return root;
}

Основная функция

int main()
{
string a1 = "vwbcyznamlp";
string a2 = "cbznywmplav";
struct TreeNode *root = constructTree(a1,a2);
printPreorder(root);
cout << endl;
system("pause");
}