二叉树的中序、前序和后序遍历(C++)

1、三种遍历方式的区别（“访问”理解为：获取节点存储的数值）

• 中序遍历：访问根节点操作发生在访问其左子树之后，在访问其右子树之前；
• 前序遍历：访问根节点操作发生在访问其左、右子树之前；
• 后序遍历：访问根节点操作发生在访问其左、右子树之后；

 2、中序遍历

2.1 中序遍历的递归方式（简单）

void inorder(TreeNode* root, vector& ans){//节点为空则直接返回if(root == nullptr) return;//先中序遍历左子树 再访问根节点 然后中序遍历右子树inorder(root->left, ans);ans.push_back(root->val);inorder(root->right, ans);
}vector inorderTraversal(TreeNode* root){//创建一个数组接收返回值vector ans;//执行以root为根节点的二叉树的中序遍历inorder(root, ans);return ans;
}

2.2 中序遍历的循环迭代方式（非递归 必掌握）

vector inorderTraversal(TreeNode* root){//创建数组用于存放打印值vector ans;//利用栈后进先出的特性将根节点存起来 便于晚一点访问stack stack;while(root != nullptr || !stack.empty()){//下面的while循环实现左子树的先遍历//遍历节点的左子树的节点的左子树...... 直到终点节点没有左子树while(root != nullptr){stack.push(root);root = root->left;}root = stack.top();stack.pop();ans.push_back(root->val);//访问完根节点后 再中序遍历其右子树root = root->right;}return ans;
}

3、前序遍历

3.1 前序遍历的递归方式（简单）

我们很容易从中序遍历的递归方式中得到启发，三种遍历方式的区别仅仅是访问根节点的时机不同，前序遍历会在路过根节点的时候直接访问它，再执行访问其左右子树，简单改一下代码顺序就可以实现

void preorder(TreeNode* root, vector& ans){if(root == nullptr) return;//先访问根节点 再分别前序遍历左右子树ans.push_back(root->val);preorder(root->left, ans);preorder(root->right, ans);
}vector preorderTraversal(TreeNode* root){vector ans;preorder(root, ans);return ans;
}

2.2 前序遍历的循环迭代方式（非递归 必掌握）

vector preorderTraversal(TreeNode* root){vector ans;stack stack;while(root != nullptr || !stack.empty()){while(root != nullptr){ans.pushback(root->val);stack.push(root);root = root->left;}root = stack.top();stack.pop();root = root->right;}return ans;
}

4、后序遍历

4.1、后序遍历的递归方式

void postorder(TreeNode* root, vector& ans){if(root == nullptr) return;postorder(root->left, ans);postorder(root->right,ans);ans.push_back(root->val);
}vector postorderTraversal(TreeNode* root){vector ans;postorder(root, ans);return ans;
}

4.2、后序遍历的循环迭代方式

和前、中序遍历有所不同，因为后序遍历需要访问完左子树后直接访问右子树，但左右子树之间是不直接相连的，而是通过根节点连在一起，所以在循环迭代中，有右子树的根节点往往需要重复压栈，具体代码实现如下：

vector postorderTraversal(TreeNode* root){vector ans;stack stack;//还需要一个变量保存上一次访问的节点 确保不会重复访问右子树TreeNode* preAccess;while(root != nullptr || !stack.empty()){while(root != nullptr){stack.push(root);root = root->left;}root = stack.top();stack.pop();//该节点没有右子树 或者已经遍历完右子树了 则打印值if(root->right == nullptr || preAccess == root->right){ans.push_back(root->val);preAccess = root;root = nullptr;}//如果节点仍有右子树 那把节点重新压回栈内 继续中序遍历其右子树else{stack.push(root);root = root->right;}}return ans;
}

学习建议：可以通过自己构造一个二叉树，用画图的方法理解代码背后具体的实现，理解完了之后背下来...... 能背就背吧

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！