原地将排序的双向链表转换为平衡二叉搜索树

2024年8月28日 | 阅读 4 分钟

在本教程中，我们将学习如何就地将已排序的双向链表 (DLL) 转换为平衡二叉搜索树 (BST)。

方法一（简单）

以下是一个简单的算法，我们首先找到链表的中间节点，并将其作为要构建的树的根。

1) 将链表的中间节点作为根。

2) 对左右两半部分递归执行相同操作。

获取左半部分的中间节点，并将其作为根的左子节点。
步骤 1：已创建
获取右半部分的中间节点，并将其作为根的右子节点。
步骤 1 导致创建了一个根。

时间复杂度为 O(nLogn)，其中 n 表示链表中的节点数。

方法二（巧妙）

方法一从根到叶构建树。我们在此方法中从叶到根构建。其概念是按照它们在双向链表中出现的精确顺序将节点添加到 BST 中，以确保树确实可以在 O(n) 时间内构建。我们首先计算给定链表中的节点数。假设计数为 n。计数节点后，我们取左侧 n/2 个节点并递归构建左子树。构建完左子树后，我们将中间节点分配给根并连接左子树到根。最后，我们递归构建右子树并将其连接到根。

在构建 BST 的同时，我们不断将链表头指针移到下一个，以便在每次递归调用中获得正确的指针。

方法二的执行如下所示。下面展示了生成平衡 BST 的主要代码。

C 语言程序

#include<stdio.h>
#include<stdlib.h>
struct Node
{
	int data;
	struct Node* next;
	struct Node* prev;
};
int countNodes ( struct Node *head );
struct Node* sortedListToBSTRecur( struct Node **head_ref, int n );
struct Node* sortedListToBST ( struct Node *head )
{
	int n = countNodes ( head );
	return sortedListToBSTRecur ( &head, n );
}
struct Node* sortedListToBSTRecur ( struct Node **head_ref, int n )
{
	if ( n <= 0 )
		return NULL;
	struct Node *left = sortedListToBSTRecur ( head_ref, n/2 );
	struct Node *root = *head_ref;
	root -> prev = left;
	*head_ref = ( *head_ref ) -> next;
	root -> next = sortedListToBSTRecur ( head_ref, n-n/2-1 );
	return root;
}
int countNodes ( struct Node *head )
{
	int count = 0;
	struct Node *temp = head;
	while( temp )
	{
		temp = temp -> next;
		count++;
	}
	return count;
}
void push ( struct Node** head_ref, int new_data )
{
	struct Node* new_node =
			( struct Node* ) malloc( sizeof ( struct Node ) );
	new_node -> data = new_data;
	new_node -> prev = NULL;
	new_node -> next = ( *head_ref );
	if ( (*head_ref ) != NULL )
	( *head_ref ) -> prev = new_node ;
	( *head_ref ) = new_node;
}
void printList ( struct Node *node )
{
	while ( node!=NULL )
	{
		printf ( "%d ", node -> data );
		node = node->next;
	}
}
void preOrder ( struct Node* node )
{
	if ( node == NULL )
		return;
	printf ( "%d ", node -> data );
	preOrder ( node->prev );
	preOrder ( node->next );
}
int main ()
{
	struct Node* head = NULL;
	push ( &head, 14 );
	push ( &head, 13 );
	push ( &head, 12 );
	push ( &head, 11 );
	push ( &head, 10 );
	push ( &head, 9 );
	push ( &head, 8 );
	printf ( "Given Linked List\n" );
	printList (head);
	struct Node *root = sortedListToBST (head);
	printf ( "\n PreOrder Traversal of constructed BST \n " );
	preOrder (root);

	return 0;
}

C++ 程序

#include <bits/stdc++.h>
using namespace std;
class Node1
{
	public:
	int data;
	Node1* next;
	Node1* prev;
};
int counttheNodes ( Node1 *head );
Node1* sortedLstToBSTRecur ( Node1 **head_ref, int no );
Node1* sortedLstToBST ( Node1 *head )
{
	int no = counttheNodes ( head );
	return sortedLstToBSTRecur ( &head, no );
}
Node1* sortedLstToBSTRecur ( Node1 **head_ref, int no )
{
	if ( no <= 0 )
		return NULL;
	Node1 *left = sortedLstToBSTRecur( head_ref, no/2 );
	Node1 *root = *head_ref;
	root -> prev = left;
	*head_ref = ( *head_ref ) -> next;
	root -> next = sortedLstToBSTRecur ( head_ref, no-no/2-1 );
	return root;
}
int counttheNodes ( Node1 *head )
{
	int count = 0;
	Node1 *temp = head;
	while ( temp )
	{
		temp = temp -> next;
		count++;
	}
	return count;
}
void push ( Node1** head_ref, int new_data )
{
	Node1* new_node = new Node1 ();
	new_node -> data = new_data;
	new_node -> prev = NULL;
	new_node -> next = ( *head_ref );
	if ( ( *head_ref ) != NULL )
	( *head_ref ) -> prev = new_node ;
	( *head_ref ) = new_node;
}
void printtheList ( Node1 *node )
{
	while ( node!=NULL )
	{
		cout << node -> data << " ";
		node = node -> next;
	}
}
void preOrder ( Node1* node )
{
	if ( node == NULL )
		return;
	cout << node -> data <<" ";
	preOrder ( node -> prev );
	preOrder ( node -> next );
}
int main ()
{
	Node1* head = NULL;
	push ( &head, 14 );
	push ( &head, 13 );
	push ( &head, 12 );
	push ( &head, 11 );
	push ( &head, 10 );
	push ( &head, 9 );
	push ( &head, 8 );
	cout << "Given Linked List\n";
	printtheList ( head );
	Node1 *root = sortedLstToBST (head);
	cout << "\nPreOrder Traversal of constructed BST \n ";
	preOrder (root);

	return 0;
}

输出

Given Linked List
8 9 10 11 12 13 14 
 PreOrder Traversal of constructed BST 
 11 9 8 10 13 12 14

时间复杂度将是 O(n)。

下一个主题合并两个平衡二叉搜索树

原地将排序的双向链表转换为平衡二叉搜索树

方法一（简单）

方法二（巧妙）

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

原地将排序的双向链表转换为平衡二叉搜索树

方法一（简单）

方法二（巧妙）

相关帖子

C 语言 Strcspn() 函数

C 语言一维数组和二维数组的区别

C 语言打印数组重复元素的程序

C 语言位域

C 语言连续文件分配程序

C 语言电费计算程序

为什么优先队列不能像普通队列那样循环？

C 语言 static_cast

C 语言的打瞌睡的理发师问题解决方案

C 语言模式匹配算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器