AcWing 3384. 二叉树遍历(挑战最复杂版本)
原题链接
简单
作者:
QQ昵称_3
,
2022-03-01 01:37:49
,
所有人可见
,
阅读 529
#include <iostream>
#include <sstream>
using namespace std;
class BinNode
{
public:
char value;
BinNode *parent;
BinNode *left;
BinNode *right;
BinNode(char, BinNode *, BinNode *, BinNode *);
~BinNode();
void insertAsLeft(char);
void insertAsRight(char);
};
BinNode::BinNode(char e, BinNode *p, BinNode *l, BinNode *r)
{
value = e;
parent = p;
left = l;
right = r;
}
BinNode::~BinNode()
{
delete left;
delete right;
}
void BinNode::insertAsLeft(char v)
{
BinNode *node = new BinNode(v, this, nullptr, nullptr);
left = node;
}
void BinNode::insertAsRight(char v)
{
BinNode *node = new BinNode(v, this, nullptr, nullptr);
right = node;
}
class BinTree
{
public:
BinNode *root;
BinTree(BinNode *);
~BinTree();
};
BinTree::BinTree(BinNode *r)
{
root = r;
}
BinTree::~BinTree()
{
}
void inOrder(BinNode *root)
{
if (root == nullptr)
return;
inOrder(root->left);
if (root->value != '#')
{
cout << root->value << " ";
}
inOrder(root->right);
}
char GetPreNode(BinNode *node)
{
BinNode *tmp = node->left;
while (tmp->right != nullptr)
{
tmp = tmp->right;
}
return tmp->value;
}
BinTree *ConstructTree()
{
BinTree *mytree = new BinTree(nullptr);
string line;
cin >> line;
stringstream ss(line);
char t;
ss >> t;
mytree->root = new BinNode(t, nullptr, nullptr, nullptr);
BinNode *tmp = mytree->root;
for (size_t i = 1; i < line.size(); i++)
{
ss >> t;
while (tmp->left != nullptr && tmp->right != nullptr)
{
tmp = tmp->parent;
}
if (tmp->left == nullptr && tmp->value != '#')
{
tmp->insertAsLeft(t);
if (t != '#')
{
tmp = tmp->left;
}
}
else if (tmp->right == nullptr && GetPreNode(tmp) == '#')
{
tmp->insertAsRight(t);
if (t == '#')
{
tmp = tmp->parent;
}
else
{
tmp = tmp->right;
}
}
}
return mytree;
}
int main()
{
BinTree *myTree = ConstructTree();
inOrder(myTree->root);
return 0;
}
把数据结构与算法作业拿过来了是吧