二叉树的遍历
/**
* 树节点
* @tparam T 泛型
*/
template<typename T>
struct TreeNode {
T data;
TreeNode *left;
TreeNode *right;
explicit TreeNode(const T &data) : data(data), left(nullptr), right(nullptr) {
}
};先序遍历
递归遍历
/**
* 递归先序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void preorderTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
std::cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}迭代遍历
/**
* 迭代先序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void preorderTraversal1(TreeNode<T> *root) {
if (root == nullptr) return;
std::stack<TreeNode<T> *> s;
s.push(root);
while (!s.empty()) {
root = s.top();
s.pop();
std::cout << root->data << " ";
if (root->right) s.push(root->right);
if (root->left) s.push(root->left);
}
}中序遍历
递归遍历
/**
* 递归中序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void inorderTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}迭代遍历
/**
* 迭代中序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void inorderTraversal1(TreeNode<T> *root) {
if (root == nullptr) return;
std::stack<TreeNode<T> *> s;
auto cur = root;
while (cur || !s.empty()) {
// 一直往左走，把所有左子节点压入栈
while (cur) {
s.push(cur);
cur = cur->left;
}
// 弹出栈顶节点并访问
cur = s.top();
s.pop();
std::cout << cur->data << " ";
// 转向右子树
cur = cur->right;
}
}后序遍历
递归遍历
/**
* 递归后序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void postorderTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->data << " ";
}迭代遍历
/**
* 迭代后序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void postorderTraversal1(TreeNode<T> *root) {
if (root == nullptr) return;
std::stack<TreeNode<T> *> s;
std::stack<T> res;
s.push(root);
while (!s.empty()) {
root = s.top();
s.pop();
res.push(root->data);
if (root->left) s.push(root->left);
if (root->right) s.push(root->right);
}
//输出
while (!res.empty()) {
std::cout << res.top() << " ";
res.pop();
}
}层序遍历
template<typename T>
void levelTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
std::queue<TreeNode<T> *> q;
q.push(root);
while (!q.empty()) {
root = q.front();
q.pop();
std::cout << root->data << " ";
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}附录
#include <bits/stdc++.h>
/**
* 树节点
* @tparam T 泛型
*/
template<typename T>
struct TreeNode {
T data;
TreeNode *left;
TreeNode *right;
explicit TreeNode(const T &data) : data(data), left(nullptr), right(nullptr) {
}
};
/**
* 递归先序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void preorderTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
std::cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
/**
* 递归中序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void inorderTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
/**
* 递归后序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void postorderTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->data << " ";
}
/**
* 迭代先序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void preorderTraversal1(TreeNode<T> *root) {
if (root == nullptr) return;
std::stack<TreeNode<T> *> s;
s.push(root);
while (!s.empty()) {
root = s.top();
s.pop();
std::cout << root->data << " ";
if (root->right) s.push(root->right);
if (root->left) s.push(root->left);
}
}
/**
* 迭代中序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void inorderTraversal1(TreeNode<T> *root) {
if (root == nullptr) return;
std::stack<TreeNode<T> *> s;
auto cur = root;
while (cur || !s.empty()) {
// 一直往左走，把所有左子节点压入栈
while (cur) {
s.push(cur);
cur = cur->left;
}
// 弹出栈顶节点并访问
cur = s.top();
s.pop();
std::cout << cur->data << " ";
// 转向右子树
cur = cur->right;
}
}
/**
* 迭代后序遍历
* @tparam T 泛型
* @param root 根节点
*/
template<typename T>
void postorderTraversal1(TreeNode<T> *root) {
if (root == nullptr) return;
std::stack<TreeNode<T> *> s;
std::stack<T> res;
s.push(root);
while (!s.empty()) {
root = s.top();
s.pop();
res.push(root->data);
if (root->left) s.push(root->left);
if (root->right) s.push(root->right);
}
//输出
while (!res.empty()) {
std::cout << res.top() << " ";
res.pop();
}
}
template<typename T>
void levelTraversal(TreeNode<T> *root) {
if (root == nullptr) return;
std::queue<TreeNode<T> *> q;
q.push(root);
while (!q.empty()) {
root = q.front();
q.pop();
std::cout << root->data << " ";
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}
int main() {
// A
// / \
// B C
// / \ \
// D E F
//前 A -> B -> D -> E -> C -> F
//中 D -> B -> E -> A -> C -> F
//后 D -> E -> B -> F -> C -> A
//层序 A B C D E F
auto A = new TreeNode<char>('A');
auto B = new TreeNode<char>('B');
auto C = new TreeNode<char>('C');
auto D = new TreeNode<char>('D');
auto E = new TreeNode<char>('E');
auto F = new TreeNode<char>('F');
A->left = B;
A->right = C;
B->left = D;
B->right = E;
C->right = F;
std::cout << "Preorder Traversal:" << std::endl;
preorderTraversal(A);
std::cout << std::endl;
preorderTraversal1(A);
std::cout << std::endl;
std::cout << "Inorder Traversal:" << std::endl;
inorderTraversal(A);
std::cout << std::endl;
inorderTraversal1(A);
std::cout << std::endl;
std::cout << "Postorder Traversal:" << std::endl;
postorderTraversal(A);
std::cout << std::endl;
postorderTraversal1(A);
std::cout << std::endl;
std::cout << "Level Traversal:" << std::endl;
levelTraversal(A);
std::cout << std::endl;
delete F;
delete E;
delete D;
delete C;
delete B;
delete A;
}
评论区(暂无评论)