二叉树遍历代码

二叉树是一种非常重要的数据结构。在很多算法和数据处理中，都会用到二叉树。而如何遍历二叉树，是我们需要掌握的技巧之一。本文将从多个角度介绍二叉树遍历代码。

一、定义

二叉树遍历是指按照某种顺序访问二叉树中的节点，可以分为前序遍历、中序遍历、后序遍历和层序遍历等四种方式。

前序遍历：根节点 -> 左子树 -> 右子树。

中序遍历：左子树 -> 根节点 -> 右子树。

后序遍历：左子树 -> 右子树 -> 根节点。

层序遍历：从上到下、从左到右依次遍历每层节点。

二、递归实现代码

递归实现是最简单的二叉树遍历方法，也是最常用的方法之一。下面是使用递归实现前序遍历、中序遍历和后序遍历的代码实现。

前序遍历：

void preOrderTraversal(TreeNode* root) {

if(root != nullptr) {

cout << root->val << " ";

preOrderTraversal(root->left);

preOrderTraversal(root->right);

}

}

中序遍历：

void inOrderTraversal(TreeNode* root) {

if(root != nullptr) {

inOrderTraversal(root->left);

cout << root->val << " ";

inOrderTraversal(root->right);

}

}

后序遍历：

void postOrderTraversal(TreeNode* root) {

if(root != nullptr) {

postOrderTraversal(root->left);

postOrderTraversal(root->right);

cout << root->val << " ";

}

}

三、迭代实现代码

除了递归实现以外，我们也可以使用迭代的方法遍历二叉树。迭代实现的代码相比递归实现更加容易理解，适用于一些特殊场景。下面是使用迭代实现前序遍历、中序遍历和后序遍历的代码实现。

前序遍历：

void preOrderTraversal(TreeNode* root) {

if(root == nullptr) {

return;

}

stack s;

s.push(root);

while(!s.empty()) {

TreeNode* top = s.top();

s.pop();

cout << top->val << " ";

if(top->right) {

s.push(top->right);

}

if(top->left) {

s.push(top->left);

}

}

}

中序遍历：

void inOrderTraversal(TreeNode* root) {

if(root == nullptr) {

return;

}

stack s;

TreeNode* cur = root;

while(!s.empty() || cur) {

if(cur) {

s.push(cur);

cur = cur->left;

}

else {

cur = s.top();

s.pop();

cout << cur->val << " ";

cur = cur->right;

}

}

}

后序遍历：

void postOrderTraversal(TreeNode* root) {

if(root == nullptr) {

return;

}

stack s;

TreeNode* cur = root;

TreeNode* pre = nullptr;

s.push(cur);

while(!s.empty()) {

cur = s.top();

if((cur->left == nullptr && cur->right == nullptr) ||

(pre && (pre == cur->left || pre == cur->right))) {

cout << cur->val << " ";

s.pop();

pre = cur;

}

else {

if(cur->right) {

s.push(cur->right);

}

if(cur->left) {

s.push(cur->left);

}

}

}

}

四、层序遍历

层序遍历比较特殊，需要使用队列实现。下面是层序遍历的代码实现。

void levelOrderTraversal(TreeNode* root) {

if(root == nullptr) {

return;

}

queue q;

q.push(root);

while(!q.empty()) {

int len = q.size();

for(int i = 0; i < len; i++) {

TreeNode* cur = q.front();

q.pop();

cout << cur->val << " ";

if(cur->left) {

q.push(cur->left);

}

if(cur->right) {

q.push(cur->right);

}

}

}

}