C语言请编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法。
时间: 2024-05-04 14:17:08 浏览: 111
C语言实现二叉树的前序、中序、后续遍历(递归法)
二叉树的中序遍历递归算法:
```c
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
```
二叉树的中序遍历非递归算法:
```c
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s; // 用栈来实现非递归遍历
TreeNode* p = root;
while (!s.empty() || p != NULL) {
if (p != NULL) {
s.push(p);
p = p->left;
} else {
p = s.top();
s.pop();
printf("%d ", p->val);
p = p->right;
}
}
}
```
二叉树的后序遍历递归算法:
```c
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
```
二叉树的后序遍历非递归算法:
```c
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (root == NULL) {
return res;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* cur = s.top();
s.pop();
res.insert(res.begin(), cur->val);
if (cur->left != NULL) {
s.push(cur->left);
}
if (cur->right != NULL) {
s.push(cur->right);
}
}
return res;
}
```
阅读全文