C编程(2)把二叉排序树的插入函数的递归算法改写为非递归算法,并在主函数中调用它,调试好程序并分析其运行结果。
时间: 2023-11-27 12:51:33 浏览: 48
二叉排序树的插入操作需要按照二叉排序树的规则将新节点插入到合适的位置上,因此可以采用递归或非递归的方式进行实现。下面是将递归算法改写为非递归算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
/* 树节点的定义 */
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
/* 创建新节点 */
Node* createNode(int data) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
/* 非递归方式插入节点 */
void insertNode(Node **root, int data) {
Node *newNode = createNode(data);
if (*root == NULL) {
*root = newNode;
return;
}
Node *current = *root;
while (1) {
if (data < current->data) {
if (current->left == NULL) {
current->left = newNode;
break;
} else {
current = current->left;
}
} else {
if (current->right == NULL) {
current->right = newNode;
break;
} else {
current = current->right;
}
}
}
}
/* 中序遍历输出二叉排序树 */
void inorderTraversal(Node *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
Node *root = NULL;
int arr[] = { 50, 30, 70, 10, 40, 60, 80 };
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) {
insertNode(&root, arr[i]);
}
inorderTraversal(root);
return 0;
}
```
该程序首先定义了二叉树节点的结构体,然后定义了创建新节点的函数。接着定义了非递归方式插入节点的函数,该函数首先创建新节点,然后在二叉排序树中查找合适的位置将新节点插入。最后定义了中序遍历输出二叉排序树的函数,并在主函数中调用这些函数。
程序的运行结果如下:
```
10 30 40 50 60 70 80
```
可以看到,程序按照从小到大的顺序输出了二叉排序树中的所有节点,说明插入操作已经正确实现。