ツリーの既知の中順遍歴と後続遍歴に基づいて階層遍歴と前順遍歴を得る
2115 ワード
#include
#include
#include
#include
using namespace std;
typedef char ElemType;
typedef struct BinTreeNode
{
ElemType data;
BinTreeNode *leftNode;
BinTreeNode *rightNode;
}BinTreeNode, *PBinTreeNode;
PBinTreeNode create_tree(int len, const char* mid,const char* bac)
{
int i;
PBinTreeNode root = new BinTreeNode;
root->data = bac[len - 1];
for (i = 0; i < len; ++i)
{
if (mid[i] == bac[len - 1])
{
break;
}
}
if (i >= len)
root = NULL;
else
{
root->leftNode = create_tree(i, mid, bac);
root->rightNode = create_tree(len - 1 - i, mid + 1 + i, bac + i);
}
return root;
}
void LevelOrder(PBinTreeNode root)
{
if (root != NULL)
{
queue qe;
qe.push(root);
while (!qe.empty())
{
root = qe.front();
qe.pop();
cout << root->data << " ";
if (root->leftNode != NULL)
{
qe.push(root->leftNode);
}
if (root->rightNode != NULL)
{
qe.push(root->rightNode);
}
}
}
}
void frontOrder(PBinTreeNode root)
{
if (NULL != root)
{
stack qe;
qe.push(root);
while (!qe.empty())
{
root = qe.top();
qe.pop();
cout << root->data << " ";
if (root->rightNode != NULL)
qe.push(root->rightNode);
if (root->leftNode != NULL)
qe.push(root->leftNode);
}
}
}
void destroy_tree(BinTreeNode *root)
{
if (root != NULL)
{
destroy_tree(root->leftNode);
destroy_tree(root->rightNode);
delete root;
root = NULL;
}
}
int main()
{
///*char mid[] = { 'c', 'b', 'a', 'e', 'd', 'f' };
//char back[] = { 'c', 'b', 'e', 'f', 'd', 'a' };*/
string mid;
string back;
cin >> mid;
cin >> back;
// int len = sizeof(mid) / sizeof(char);
int len = mid.size();
PBinTreeNode pRoot = create_tree(len, mid.c_str(), back.c_str());
LevelOrder(pRoot);
destroy_tree(pRoot);
}