给定的二叉树使用层次遍历的顺序输入,你需要构造二叉树并实现非递归的中序遍历。以下是使用C语言的方法:
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 栈节点
typedef struct StackNode {
TreeNode* treeNode;
struct StackNode* next;
} StackNode;
// 入栈
void push(StackNode** stack, TreeNode* treeNode) {
StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
new_node->treeNode = treeNode;
new_node->next = *stack;
*stack = new_node;
}
// 出栈
TreeNode* pop(StackNode** stack) {
if (*stack == NULL) {
return NULL;
}
StackNode* temp = *stack;
*stack = (*stack)->next;
TreeNode* treeNode = temp->treeNode;
free(temp);
return treeNode;
}
// 检查栈是否为空
int isEmpty(StackNode* stack) {
return stack == NULL;
}
// 新建树节点
TreeNode* newTreeNode(int value) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = value;
node->left = node->right = NULL;
return node;
}
// 构造二叉树函数,使用队列
TreeNode* buildTree(int arr[], int n) {
if (n <= 0) return NULL;
TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);
for (int i = 0; i < n; i++) {
nodes[i] = (arr[i] != -1) ? newTreeNode(arr[i]) : NULL;
}
int j = 1;
for (int i = 0; i < n && j < n; i++) {
if (nodes[i] != NULL) {
if (j < n) nodes[i]->left = nodes[j++];
if (j < n) nodes[i]->right = nodes[j++];
}
}
TreeNode* root = nodes[0];
free(nodes);
return root;
}
// 中序遍历非递归实现
void inorderTraversal(TreeNode* root) {
StackNode* stack = NULL;
TreeNode* curr = root;
while (curr != NULL || !isEmpty(stack)) {
// 向左遍历并入栈
while (curr != NULL) {
push(&stack, curr);
curr = curr->left;
}
// 出栈并访问
curr = pop(&stack);
printf("%d ", curr->val);
// 访问右子树
curr = curr->right;
}
}
// 主函数
int main() {
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
TreeNode* root = buildTree(arr, n);
inorderTraversal(root);
printf("\n");
return 0;
}
注意:
- 树节点使用`-1`表示`None`,表示输入时不存在的节点。
- 实现了一个简单的堆栈来协助中序遍历。
- `buildTree`函数构建二叉树时,假设输入按层次顺序。
- 中序遍历依次访问左子树、根节点、右子树的顺序。
以上代码中使用了简单的堆栈结构实现对树的非递归中序遍历。请确保输入按照树的层次顺序,否则构建的二叉树可能不符合预期。
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。 |