用c语言实现从键盘或文件输入若干个点,构造一棵二叉排序树,然后将此树转换为一个有序的双向链表,并按顺序输出双向链表中各个结点的值。
时间: 2024-02-17 21:00:45 浏览: 85
二叉排序树的C语言实现
5星 · 资源好评率100%
好的,这是一个关于数据结构的问题,下面是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的结构体
typedef struct BSTNode {
int val;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
// 定义双向链表的结构体
typedef struct ListNode {
int val;
struct ListNode* prev;
struct ListNode* next;
} ListNode;
// 将节点插入到双向链表尾部
void insertIntoList(ListNode** head, ListNode** tail, BSTNode* node) {
ListNode* listNode = (ListNode*)malloc(sizeof(ListNode));
listNode->val = node->val;
listNode->prev = *tail;
listNode->next = NULL;
if (!*head) {
*head = *tail = listNode;
} else {
(*tail)->next = listNode;
*tail = listNode;
}
}
// 将二叉排序树转换为有序双向链表
void convertBSTToList(BSTNode* root, ListNode** head, ListNode** tail) {
if (!root) {
return;
}
convertBSTToList(root->left, head, tail);
insertIntoList(head, tail, root);
convertBSTToList(root->right, head, tail);
}
// 按顺序输出双向链表中各个结点的值
void printList(ListNode* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
// 构造二叉排序树并转换为有序双向链表
void constructBSTAndConvertToList() {
BSTNode* root = NULL;
int value;
while (scanf("%d", &value) != EOF) {
BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
node->val = value;
node->left = node->right = NULL;
if (!root) {
root = node;
} else {
BSTNode* cur = root;
BSTNode* parent = NULL;
while (cur) {
parent = cur;
if (value < cur->val) {
cur = cur->left;
} else {
cur = cur->right;
}
}
if (value < parent->val) {
parent->left = node;
} else {
parent->right = node;
}
}
}
ListNode* head = NULL;
ListNode* tail = NULL;
convertBSTToList(root, &head, &tail);
printList(head);
// 释放动态分配的内存
while (head) {
ListNode* next = head->next;
free(head);
head = next;
}
while (root) {
BSTNode* left = root->left;
BSTNode* right = root->right;
free(root);
root = NULL;
constructBSTAndConvertToList();
}
}
int main() {
constructBSTAndConvertToList();
return 0;
}
```
注意,本代码中的二叉排序树和有序双向链表都是动态分配的,需要在使用完毕后手动释放内存。另外,对于大量数据的情况,由于递归深度过深,可能会导致栈溢出,可以使用非递归方式实现中序遍历来避免这个问题。
阅读全文