用C语言:二叉树采用二叉链表存储结构,要求既不用递归也不用栈,返回二叉树后序遍历序列中第一个结点的指针。
时间: 2024-03-14 16:45:18 浏览: 16
好的,以下是用C语言实现不用递归也不用栈的二叉树后序遍历算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// Morris遍历算法实现后序遍历
TreeNode* postorderTraversal(TreeNode* root) {
if (!root) return NULL;
TreeNode *res = NULL, *cur = root;
while (cur) {
if (!cur->right) {
res = (!res) ? cur : res;
cur = cur->left;
} else {
TreeNode *mostRight = cur->right;
while (mostRight->left && mostRight->left != cur) {
mostRight = mostRight->left;
}
if (!mostRight->left) {
mostRight->left = cur;
cur = cur->right;
} else {
mostRight->left = NULL;
res = (!res) ? cur : res;
cur = cur->left;
}
}
}
return res;
}
// 创建二叉树
TreeNode* createBinaryTree(int arr[], int len, int index) {
if (index >= len || arr[index] == -1) return NULL;
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = arr[index];
root->left = createBinaryTree(arr, len, index * 2 + 1);
root->right = createBinaryTree(arr, len, index * 2 + 2);
return root;
}
// 打印二叉树
void printBinaryTree(TreeNode *root) {
if (!root) return;
printf("%d ", root->val);
printBinaryTree(root->left);
printBinaryTree(root->right);
}
int main() {
int arr[] = {1, 2, 3, 4, 5, -1, 6, -1, -1, 7, 8};
int len = sizeof(arr) / sizeof(int);
TreeNode *root = createBinaryTree(arr, len, 0);
printf("原始二叉树:");
printBinaryTree(root);
printf("\n后序遍历序列:");
TreeNode *res = postorderTraversal(root);
while (res) {
printf("%d ", res->val);
res = res->left;
}
printf("\n");
return 0;
}
```
上述代码中,我使用了Morris遍历算法实现了二叉树的后序遍历,同时也提供了创建二叉树和打印二叉树的函数,可供测试使用。