-
Notifications
You must be signed in to change notification settings - Fork 0
/
Week5Exercise2.cpp
75 lines (75 loc) · 2.88 KB
/
Week5Exercise2.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <cstring>
struct treeNode {
char comp;
long layer;
treeNode *leftTree, *rightTree, *father;
treeNode(char c, long l) : comp(c), layer(l), leftTree(nullptr), rightTree(nullptr), father(nullptr) {}
inline char* preOrderTravel() { return preOrderTravel(this); }
inline char* midOrderTravel() { return midOrderTravel(this); }
inline char* postOrderTravel() { return postOrderTravel(this); }
inline char* preOrderTravel(treeNode* t) {
if (t == nullptr) return nullptr;
char* leftOrder = preOrderTravel(t->leftTree);
char* rightOrder = preOrderTravel(t->rightTree);
long leftlen = (leftOrder == nullptr) ? 0 : strlen(leftOrder);
long rightlen = (rightOrder == nullptr) ? 0 : strlen(rightOrder);
char* travelOrder = new char[leftlen + rightlen + 1];
memset(travelOrder, 0, sizeof(travelOrder));
travelOrder[0] = t->comp;
if (leftlen) strcat(travelOrder, leftOrder);
if (rightlen) strcat(travelOrder, rightOrder);
return travelOrder;
}
inline char* midOrderTravel(treeNode* t) {
if (t == nullptr) return nullptr;
char* leftOrder = midOrderTravel(t->leftTree);
char* rightOrder = midOrderTravel(t->rightTree);
long leftlen = (leftOrder == nullptr) ? 0 : strlen(leftOrder);
long rightlen = (rightOrder == nullptr) ? 0 : strlen(rightOrder);
char* travelOrder = new char[leftlen + rightlen + 1];
memset(travelOrder, 0, sizeof(travelOrder));
if (leftlen) strcat(travelOrder, leftOrder);
travelOrder[leftlen] = t->comp;
if (rightlen) strcat(travelOrder, rightOrder);
return travelOrder;
}
inline char* postOrderTravel(treeNode* t) {
if (t == nullptr) return nullptr;
char* leftOrder = postOrderTravel(t->leftTree);
char* rightOrder = postOrderTravel(t->rightTree);
long leftlen = (leftOrder == nullptr) ? 0 : strlen(leftOrder);
long rightlen = (rightOrder == nullptr) ? 0 : strlen(rightOrder);
char* travelOrder = new char[leftlen + rightlen + 1];
memset(travelOrder, 0, sizeof(travelOrder));
if (leftlen) strcat(travelOrder, leftOrder);
if (rightlen) strcat(travelOrder, rightOrder);
travelOrder[leftlen + rightlen] = t->comp;
return travelOrder;
}
};
treeNode *tree, *curNode, *tempNode;
char str[200];
long len, flag;
int main() {
while (scanf("%s", str) != EOF) {
if (!strcmp(str, "0")) break;
len = strlen(str);
if (len == 1) tree = new treeNode(str[0], 0), curNode = tree;
else if (str[len - 1] == '*') flag = 1;
else {
while (curNode->layer >= len - 1) curNode = curNode->father;
tempNode = new treeNode(str[len - 1], len - 1);
if ((curNode->leftTree != nullptr) || (flag)) {
tempNode->father=curNode, curNode->rightTree = tempNode, curNode = curNode->rightTree;
}
else {
tempNode->father = curNode, curNode->leftTree = tempNode, curNode = curNode->leftTree;
}
flag = 0;
}
}
printf("%s\n", tree->preOrderTravel());
printf("%s\n", tree->postOrderTravel());
printf("%s\n", tree->midOrderTravel());
}