用C语言设计一种二叉树的数据,生成它(此时不能用递归方式),完全生成后,再用递归的方式调用它会爆栈,运行并输出递归深度,最终获得爆栈的结果。 给出你的设计和生成它的方法,附上代码和爆栈运行的结果
时间: 2024-09-28 18:05:07 浏览: 12
在C语言中,我们可以使用结构体来表示二叉树节点,并创建一个链表式的结构来存储整个二叉树,而非递归生成。这是因为非递归的方式避免了在内存栈上频繁的函数调用,防止栈溢出。首先,我们定义一个二叉树节点:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子节点
struct TreeNode* right; // 右子节点
} TreeNode;
// 创建新节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 生成非递归的二叉树
void buildTree(TreeNode** root, int values[], int start, int end) {
if (start > end) {
return;
}
int mid = (start + end) / 2;
TreeNode* node = createNode(values[mid]);
*root = node;
buildTree(&node->left, values, start, mid - 1);
buildTree(&node->right, values, mid + 1, end);
}
```
现在我们可以生成一个示例二叉树:
```c
int main() {
int values[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(values) / sizeof(values[0]);
TreeNode* root = NULL;
buildTree(&root, values, 0, size - 1);
// 输出节点值(这里仅作演示,实际应用中你可以选择其他合适的方式来遍历)
void printInOrder(TreeNode* node) {
if (node != NULL) {
printInOrder(node->left);
printf("%d ", node->val);
printInOrder(node->right);
}
}
printInOrder(root);
return 0;
}
```
由于我们在main函数中直接生成并打印了树,所以没有涉及到递归调用导致的栈溢出。如果要尝试递归地访问这个生成的树并计算深度,可以添加一个辅助函数:
```c
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth) ? leftDepth + 1 : rightDepth + 1;
}
int main() {
... // 上面的主函数部分
int treeDepth = maxDepth(root);
printf("递归最大深度: %d\n", treeDepth); // 这里会正常返回树的深度,不会爆栈
return 0;
}
```