二叉树前序遍历的算法思想
时间: 2023-08-13 14:40:36 浏览: 47
二叉树的前序遍历算法思想是先访问根节点,然后按照左子树、右子树的顺序递归遍历每个子树。具体实现过程可以采用递归方式或者利用栈来实现迭代遍历。
递归方式实现前序遍历:
1. 访问根节点;
2. 递归遍历左子树;
3. 递归遍历右子树。
具体实现代码如下:
```
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
cout << root->val << " "; //访问根节点
preOrderTraversal(root->left); //递归遍历左子树
preOrderTraversal(root->right); //递归遍历右子树
}
}
```
利用栈实现前序遍历:
1. 将根节点入栈;
2. 循环执行以下操作:
- 弹出栈顶元素并访问;
- 先将右子树入栈(如果存在);
- 再将左子树入栈(如果存在)。
具体实现代码如下:
```
void preOrderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
cout << node->val << " "; //访问当前节点
if (node->right != NULL) st.push(node->right); //右子树入栈
if (node->left != NULL) st.push(node->left); //左子树入栈
}
}
```
以上是二叉树前序遍历的算法思想和实现方法。其中,利用栈实现的迭代遍历方式比递归方式更节省空间,并且可以避免递归调用栈溢出的问题。