节点结构
struct node {
int val;
struct node *left;
struct node *right;
};
前序遍历
void pre_order_traveral(struct node *head) {
std::stack<struct node *> data_stack;
data_stack.emplace(head);
while(!data_stack.empty()) {
struct node *n = data_stack.top();
data_stack.pop();
std::cout << n->val << " ";
if (n->right != nullptr) {
data_stack.emplace(n->right);
}
if (n->left != nullptr) {
data_stack.emplace(n->left);
}
}
}
中序遍历
void mid_order_traveral(struct node *head) {
std::stack<struct node*> data_stack;
data_stack.emplace(head);
while(!data_stack.empty()) {
struct node *n = data_stack.top();
struct node *left = n->left;
struct node *right = n->right;
data_stack.pop();
if (left == nullptr && right == nullptr) {
std::cout << n->val << " ";
continue;
}
if (right != nullptr) {
data_stack.emplace(right);
}
n->left = nullptr;
n->right = nullptr;
data_stack.emplace(n);
if (left != nullptr) {
data_stack.emplace(left);
}
}
}
后序遍历
void post_order_traveral(struct node *head) {
std::stack<struct node*> data_stack;
data_stack.emplace(head);
while(!data_stack.empty()) {
struct node *n = data_stack.top();
data_stack.pop();
struct node *left = n->left;
struct node *right = n->right;
if (left == nullptr && right == nullptr) {
std::cout << n->val << " ";
continue;
}
n->left = nullptr;
n->right = nullptr;
data_stack.emplace(n);
if (right != nullptr) {
data_stack.emplace(right);
}
if (left != nullptr) {
data_stack.emplace(left);
}
}
}
层序遍历
void level_order_traveral(struct node *head) {
std::queue<struct node*> data_queue;
data_queue.emplace(head);
while (!data_queue.empty()) {
int visit_size = data_queue.size();
for (int i = 0; i < visit_size; ++i) {
struct node * n = data_queue.front();
data_queue.pop();
std::cout << n->val << " ";
if (n->left != nullptr) {
data_queue.emplace(n->left);
}
if (n->right != nullptr) {
data_queue.emplace(n->right);
}
}
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论