Formula-Tree/Tree.cpp at main · L1SP/Formula-Tree · GitHub

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include "Tree.h"
#include "Stack.h"
#include "Queue.h"
Tree::Tree() {
	root = nullptr;
}
Tree::~Tree() {
	clear();
}

void Tree::clear(TreeNode*& node) {
	if (node) {
		clear(node->left);
		clear(node->right);
		delete node;
		node = nullptr;
	}
}
void Tree::clear() {
	clear(root);
}
void Tree::print(const std::string& prefix, const TreeNode* node, bool isLeft) {
	if (node) {
		std::cout << prefix;
		std::cout << (isLeft ? u8"├── " : u8"└── ");
		std::cout << node->val << std::endl;
		print(prefix + (isLeft ? u8"│   " : u8"    "), node->left, true);
		print(prefix + (isLeft ? u8"│   " : u8"    "), node->right, false);
	}
}
void Tree::print() {
	print("", root, false);
}
void Tree::parseToTree(std::string postfix) {
	TreeStack* st = new TreeStack;
	TreeNode* temp_tree1;
	TreeNode* temp_tree2;
	for (unsigned int i = 0; i < postfix.length(); ++i) {
		if (!(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*'))
		{
			root = new TreeNode(postfix[i]);
			st->push(root);
		}
		else
		{
			root = new TreeNode(postfix[i]);
			temp_tree1 = st->pop();
			temp_tree2 = st->pop();
			root->right = temp_tree1;
			root->left = temp_tree2;
			st->push(root);
		}
	}
	delete st;
}
Tree::TreeNode* Tree::copyInOrder(Tree::TreeNode* root) {
	if (root == nullptr)
		return nullptr;
	else {
		TreeNode* tmp = new TreeNode;
		tmp->val = root->val;
		tmp->right = copyInOrder(root->right);
		tmp->left = copyInOrder(root->left);
		return tmp;
	}
}
void Tree::treeTransform() {
	treeTransform(root);
}
void Tree::treeTransform(TreeNode* r) {
	TreeNode* copyTree1;
	TreeNode* copyTree2;
	if (!r)
		return;
	if (r->left && (r->left->val == '-' || r->left->val == '+')) {
		char sign = r->left->val;
		copyTree1 = copyInOrder(r->right);
		delete r->right->left;
		delete r->right->right;
		copyTree2 = copyInOrder(r->left->right);
		delete r->left->right;
		r->left->val = '*';
		r->val = sign;
		r->right->val = '*';
		r->right->right = copyTree1;
		r->right->left = copyTree2;
		r->left->right = copyInOrder(copyTree1);
		treeTransform(r);
		treeTransform(r->left);
		treeTransform(r->right);
	}
	else if (r->right && (r->right->val == '-' || r->right->val == '+')) {
		char sign = r->right->val;
		copyTree1 = copyInOrder(r->left);
		delete r->left->left;
		delete r->left->right;
		copyTree2 = copyInOrder(r->right->left);
		delete r->right->left;
		r->left->val = '*';
		r->val = sign;
		r->right->val = '*';
		r->left->left = copyTree1;
		r->left->right = copyTree2;
		r->right->left = copyInOrder(copyTree1);
		treeTransform(r);
		treeTransform(r->left);
		treeTransform(r->right);
	}
	else {
		treeTransform(r->left);
		treeTransform(r->right);
	}


}