c++实现中序遍历二叉树的递归算法和非递归算法
时间: 2023-11-14 09:11:37 浏览: 39
以下是中序遍历二叉树的递归算法和非递归算法的实现代码,供您参考:
递归算法:
```
void inorder_recursive(TreeNode* root) {
if (root) {
inorder_recursive(root->left);
cout << root->val << " ";
inorder_recursive(root->right);
}
}
```
非递归算法:
```
void inorder_nonrecursive(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* curr = root;
while (curr || !stk.empty()) {
while (curr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top();
stk.pop();
cout << curr->val << " ";
curr = curr->right;
}
}
```
请注意,这里的 `TreeNode` 结构体是二叉树节点的定义,其中包含了节点的值、左子节点和右子节点。如果您需要使用这些代码,请先自行定义 `TreeNode` 结构体。
相关问题
用c++语言写二叉树中序遍历的递归算法
二叉树的中序遍历是指先遍历左子树,再遍历根节点,最后遍历右子树。
递归算法的核心思想是先递归遍历左子树,然后输出根节点,最后递归遍历右子树。
下面是用 C++ 语言写二叉树中序遍历的递归算法的代码:
```cpp
#include <iostream>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 中序遍历的递归算法
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left); // 递归遍历左子树
cout << root->val << " "; // 输出根节点
inorderTraversal(root->right); // 递归遍历右子树
}
int main() {
// 创建二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 中序遍历二叉树
inorderTraversal(root);
cout << endl;
return 0;
}
```
输出结果为:
```
4 2 5 1 3
```
说明递归算法实现了二叉树的中序遍历。
用c➕➕实现中序遍历二叉树T的非递归算法
好的,下面是使用 C++ 实现中序遍历二叉树T的非递归算法的代码,同样假设二叉树节点类型为TreeNode,具有val、left、right三个属性:
```c++
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur != nullptr || !s.empty()) {
while (cur != nullptr) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}
```
该算法与之前的 Java 实现类似,同样使用了一个栈来辅助遍历。不同的是,使用 C++ 需要注意一些细节,如栈的声明方式为 stack<TreeNode*>,表示存储指向 TreeNode 对象的指针;访问 TreeNode 的属性需要使用箭头符号 ->。