二叉树的非递归遍历c语言
时间: 2023-09-21 13:10:40 浏览: 57
以下是二叉树的非递归遍历的C语言代码实现:
1. 非递归先序遍历
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
printf("%d ", node->val);
if (node->right != NULL) {
stk.push(node->right);
}
if (node->left != NULL) {
stk.push(node->left);
}
}
}
```
2. 非递归中序遍历
```
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> stk;
TreeNode* node = root;
while (node != NULL || !stk.empty()) {
while (node != NULL) {
stk.push(node);
node = node->left;
}
node = stk.top();
stk.pop();
printf("%d ", node->val);
node = node->right;
}
}
```
3. 非递归后序遍历
```
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> stk1, stk2;
stk1.push(root);
while (!stk1.empty()) {
TreeNode* node = stk1.top();
stk1.pop();
stk2.push(node);
if (node->left != NULL) {
stk1.push(node->left);
}
if (node->right != NULL) {
stk1.push(node->right);
}
}
while (!stk2.empty()) {
TreeNode* node = stk2.top();
stk2.pop();
printf("%d ", node->val);
}
}
```
以上是二叉树的非递归遍历的C语言代码实现,其中用到了栈的数据结构,通过栈的先进后出特性实现二叉树的遍历。