二叉树的遍历csdn
二叉树是数据结构中一种比较基础的结构，也是非常常用的数据结构，对于数据结构的学习来说，学习二叉树是非常必要的。对于二叉树的遍历也是需要掌握的，所以对于二叉树遍历的学习也是必不可少的。
在二叉树的遍历中，遍历的方式主要有三种，分别是前序遍历、中序遍历和后序遍历。在三种遍历方式中，每种方式的遍历顺序是不同的，由此获得的信息也是不同的。下面将从三种遍历方式分别来介绍一下。
一、前序遍历
前序遍历是二叉树的一种遍历方式，这种方式的遍历顺序是先遍历根节点，再遍历左子树，最后遍历右子树。从前序遍历得到的信息是树的层级结构以及一些规律。对于前序遍历可以从递归和非递归两个方面来进行学习。
递归的前序遍历代码如下：
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << endl;
preOrder(root->left);
preOrder(root->right);
}
非递归的前序遍历代码如下：
void preOrder(TreeNode* root) {
stack
st.push(root);
while (!st.empty()) {
auto node = st.top();
cout << node->val << endl;
st.pop();
if (node->right != nullptr) {
st.push(node->right);
}
if (node->left != nullptr) {
st.push(node->left);
}
}
}
二、中序遍历
中序遍历是二叉树的另一种遍历方式，这种遍历方式的遍历顺序是先遍历左子树，再遍历根节点，最后遍历右子树。从中序遍历得到的信息是树的最左边节点到最右边节点的一个有序排列。对于中序遍历可以从递归和非递归两个方面来进行学习。
递归的中序遍历代码如下：
void inOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
inOrder(root->left);
cout << root->val << endl;
inOrder(root->right);
}
非递归的中序遍历代码如下：
void inOrder(TreeNode* root) {
stack
auto p = root;
while (p != nullptr || !st.empty()) {
if (p != nullptr) {
st.push(p);
p = p->left;
} else {
auto node = st.top();
st.pop();
cout << node->val << endl;
p = node->right;
}
}
}
三、后序遍历
后序遍历是二叉树的最后一种遍历方式，这种方式的遍历顺序是先遍历左子树，再遍历右子树，最后遍历根节点。从后序遍历得到的信息是树的叶子节点的排列和树的层级结构。对于后序遍历可以从递归和非递归两个方面来进行学习。
递归的后序遍历代码如下：
void postOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << endl;
}
非递归的后序遍历代码如下：
void postOrder(TreeNode* root) {
stack
st1.push(root);
while (!st1.empty()) {
auto node = st1.top();
st2.push(node);
st1.pop();
if (node->left != nullptr) {
st1.push(node->left);
}
if (node->right != nullptr) {
st1.push(node->right);
}
}
while(!st2.empty()){
auto node = st2.top();
cout<
st2.pop();
}
}
综上所述，学习二叉树遍历，可以通过前序遍历、中序遍历和后序遍历三种方式来掌握，每种方式的遍历顺序和获得的信息都是不同的。在编程的实现上，可以通过递归和非递归两种方式来实现。
