非递归二叉树的创建c++
时间: 2024-01-13 15:04:18 浏览: 24
您好!要创建一个非递归二叉树,您可以使用栈数据结构来辅助实现。下面是一个示例的C代码,用于创建非递归二叉树:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 二叉树节点的定义
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 栈节点的定义
struct StackNode {
struct TreeNode* data;
struct StackNode* next;
};
// 判断栈是否为空
bool isEmpty(struct StackNode* root) {
return !root;
}
// 入栈
void push(struct StackNode** root, struct TreeNode* data) {
struct StackNode* newNode = (struct StackNode*)malloc(sizeof(struct StackNode));
newNode->data = data;
newNode->next = *root;
*root = newNode;
}
// 出栈
struct TreeNode* pop(struct StackNode** root) {
if (isEmpty(*root))
return NULL;
struct StackNode* temp = *root;
*root = (*root)->next;
struct TreeNode* popped = temp->data;
free(temp);
return popped;
}
// 创建二叉树
struct TreeNode* createBinaryTree() {
struct TreeNode* root = NULL;
struct StackNode* stack = NULL;
int data;
printf("请输入根节点的值(-1表示空节点):");
scanf("%d", &data);
if (data == -1)
return NULL;
root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->data = data;
root->left = root->right = NULL;
push(&stack, root);
while (!isEmpty(stack)) {
struct TreeNode* currentNode = pop(&stack);
printf("请输入节点 %d 的左子节点的值(-1表示空节点):", currentNode->data);
scanf("%d", &data);
if (data != -1) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
currentNode->left = newNode;
push(&stack, newNode);
}
printf("请输入节点 %d 的右子节点的值(-1表示空节点):", currentNode->data);
scanf("%d", &data);
if (data != -1) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
currentNode->right = newNode;
push(&stack, newNode);
}
}
return root;
}
// 前序遍历二叉树
void preorderTraversal(struct TreeNode* root) {
if (root == NULL)
return;
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 主函数
int main() {
struct TreeNode* root = createBinaryTree();
printf("前序遍历结果为:");
preorderTraversal(root);
return 0;
}
```
这段代码首先使用栈数据结构来辅助创建二叉树。它从根节点开始,逐层输入每个节点的左子节点和右子节点的值,如果子节点的值为-1,则表示为空节点。
最后,它通过前序遍历将二叉树的节点值输出。
希望能帮到您!如果有任何问题,请随时提问。