#include<iostream>
#include<iomanip>
#include<string>
#include<queue>
#include<vector>
#include<stdlib.h>
using namespace std;
template<typename T>
class TreeNode {
public:
T data;
TreeNode<T> *leftChild;
TreeNode<T> *rightChild;
TreeNode(T data) {
this->data = data;
this->rightChild = NULL;
this->rightChild = NULL;
}
};
template<typename T>
class BinaryTree {
private:
TreeNode<T> *root;
public:
BinaryTree(T data);
TreeNode<T>* getroot();
void InsertLeft(TreeNode<T> *p, T data);
void InsertRight(TreeNode<T> *p, T data);
TreeNode<T>* Search(TreeNode<T> *root, T data);
void PreOrder(TreeNode<T> *root);
void InOrder(TreeNode<T> *root);
void PostOrder(TreeNode<T> *root);
};
template<typename T>
BinaryTree<T>::BinaryTree(T data) {
TreeNode<T> *newnode = new TreeNode<T>(data);
root = newnode;
}
template<typename T>
TreeNode<T>* BinaryTree<T>::getroot() {
return root;
}
template<typename T>
void BinaryTree<T>::InsertLeft(TreeNode<T> *p, T data) {
TreeNode<T> *newnode = new TreeNode<T>(data);
newnode->leftChild = p->leftChild;
p->leftChild = newnode;
}
template<typename T>
void BinaryTree<T>::InsertRight(TreeNode<T> *p, T data) {
TreeNode<T> *newnode = new TreeNode<T>(data);
newnode->rightChild = p->rightChild;
p->rightChild = newnode;
}
template<typename T>
TreeNode<T>* BinaryTree<T>::Search(TreeNode<T> *root, T data) {
queue<TreeNode<T>*> queue;
TreeNode<T> *q = NULL;
queue.push(root);
while (!queue.empty()) {
TreeNode<T> *p = queue.front();
queue.pop();
if (p->data == data) {
q = p;
}
if (p->leftChild != NULL) {
queue.push(p->leftChild);
}
if (p->rightChild != NULL) {
queue.push(p->rightChild);
}
}
return q;
}
template<typename T>
void BinaryTree<T>::PreOrder(TreeNode<T>* root) {
if (root != NULL) {
cout << root->data;
PreOrder(root->leftChild);
PreOrder(root->rightChild);
}
}
template<typename T>
void BinaryTree<T>::InOrder(TreeNode<T> *root) {
if (root != NULL) {
InOrder(root->leftChild);
cout << root->data;
InOrder(root->rightChild);
}
}
template<typename T>
void BinaryTree<T>::PostOrder(TreeNode<T> *root) {
if (root != NULL) {
PostOrder(root->leftChild);
PostOrder(root->rightChild);
cout << root->data;
}
}
int main() {
string str;
while (cin >> str) {
BinaryTree<char> *bin = new BinaryTree<char>(str[0]);
TreeNode<char> *root = bin->getroot();
for (int i = 1; i < str.length(); i++) {
if (str[i] != '.') {
TreeNode<char> *p = bin->Search(root, str[(i - 1) / 2]);
if (i % 2 == 0) {
bin->InsertRight(p, str[i]);
}
else {
bin->InsertLeft(p, str[i]);
}
}
}
bin->PreOrder(root);
cout << endl;
}
return 0;
}
测试数据
ABCDEFGHIJKL
A.B...C.......D
ABCD.EF.G
T
ABC.D.E..FG...H
输出
ABDHIEJKCFLG
ABCD
ABDGCEF
T
ABDFGCEH