数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究从其链表表示构建完全二叉树
在这个问题中，我们将把链表转换为完全二叉树。
我们可以将链表视为数组。链表的第 p 个元素是二叉树的第 2*p + 1 和 2*p + 2 个元素的父节点。因此，我们可以遍历链表的每个元素并构建二叉树。
问题陈述 - 我们给定一个包含 N 个节点的链表。我们需要从给定的链表构建完全二叉树。还要打印二叉树的中序遍历。
注意 - 在完全二叉树中，除了树的最后一层外，树的所有层都已完全填充。
示例
输入
L_head = 48 -> 142 -> 18 -> 72 -> 10 -> 12 -> 94 -> 45
输出
45, 72, 142, 10, 48, 12, 18, 94
48
/ \
142 18
/ \ / \
72 10 12 94
/
45
说明 - 中序遍历首先打印左子树，然后打印根节点，最后打印右子树。
输入
L_head = 2 -> 8 -> 4 -> 5
输出
5, 8, 2, 4
2
/ \
8 4
/
5
说明 - 我们打印了给定二叉树的中序遍历。
输入
L_head = NULL
输出
NULL
说明 - 二叉树为空，因为链表不包含任何节点。
方法
在链表中，第 P 个节点是二叉树中 (2*p + 1) 和 (2*p + 2) 节点的父节点。
我们将使用队列数据结构来跟踪二叉树的节点。使用链表元素创建二叉树的节点后，我们将树节点推入队列。此外，在每次迭代中，我们从队列中弹出节点，从链表中获取接下来的 2 个节点，并为当前节点创建左子节点和右子节点，并将它们与父节点连接。
算法
步骤 1 - 为链表创建一个 L_Node 结构，其中包含 'val' 整数变量和 'next' 指针。
步骤 2 - 为二叉树创建一个 'B_Node' 结构，其中包含 'val' 整数和 'left' 和 'child' 指针。
步骤 3 - 接下来，定义 insertInList() 函数来创建链表。
步骤 3.1 - 在 insertInList() 函数中，定义一个新的 L_Node。
步骤 3.2 - 初始化新节点的值。此外，将新节点的 'next' 指针初始化为头节点，以便将新节点插入到链表的开头。
步骤 3.3 - 使用新节点更新头节点。
步骤 4 - 定义 createNewNode() 函数来为二叉树创建一个新节点。
步骤 5 - 定义 listTOBinary() 函数将链表转换为二叉树。
步骤 6 - 如果 L_head 为 NULL，则将 B_head 更新为 NULL，并执行 return 语句。
步骤 7 - 使用链表的 L_Node 的值创建一个新的二叉树节点，并将其存储在 B_head 中。此外，将 B_head 插入队列并将 L_head 指向下一个节点。
步骤 8 - 遍历链表。
步骤 8.1 - 从队列中弹出第一个节点并将其存储在 'parent' 节点中。此外，创建 'l_child' 和 'r_child' 指针并初始化为 NULL。
步骤 8.2 - 为二叉树创建一个新节点，使用 L_head 节点的值初始化，并将其存储到 l_child 节点中。
步骤 8.3 - 将 l_child 节点插入队列，并将 L_head 移动到下一个节点。
步骤 8.4 - 如果 l_head 不为空，则创建一个新节点，并将其分配给 r_child 节点。此外，将 r_child 节点插入队列并将 L_head 移动到下一个节点。
步骤 9 - 使用 l_child 和 r_child 节点更新父节点的左指针和右指针。
步骤 10 - 创建 inorder() 函数以显示新创建树的中序遍历。
示例
#include <iostream>
#include <string>
#include <queue>
using namespace std;
// Structure for tree and linked list
struct L_Node {
int val;
L_Node *next;
};
struct B_Node {
int val;
B_Node *left, *right;
};
// To insert a node in a linked list
void InsertInList(struct L_Node **head, int new_val) {
struct L_Node *temp_node = new L_Node;
temp_node->val = new_val;
// Insert node at start
temp_node->next = (*head);
// Change head node pointer
(*head) = temp_node;
}
// For Creating a new node for the tree
B_Node *createNewNode(int val) {
B_Node *temp_node = new B_Node;
temp_node->val = val;
temp_node->left = temp_node->right = NULL;
return temp_node;
}
void listTOBinary(L_Node *L_head, B_Node *&B_head) {
queue<B_Node *> que;
// For empty linked list
if (L_head == NULL) {
B_head = NULL;
return;
}
// Initialize the head node of the binary tree
B_head = createNewNode(L_head->val);
que.push(B_head);
// Move list pointer
L_head = L_head->next;
// Traverse until we reach at the end of the list
while (L_head) {
// Take node from queue
B_Node *parent = que.front();
que.pop();
// Add the next two nodes as a child of the parent node
B_Node *l_child = NULL, *r_child = NULL;
l_child = createNewNode(L_head->val);
que.push(l_child);
L_head = L_head->next;
if (L_head) {
r_child = createNewNode(L_head->val);
que.push(r_child);
L_head = L_head->next;
}
parent->left = l_child;
parent->right = r_child;
}
}
void inorder(B_Node *B_head) {
if (B_head) {
inorder(B_head->left);
cout << B_head->val << " ";
inorder(B_head->right);
}
}
int main() {
struct L_Node *L_head = NULL;
InsertInList(&L_head, 45);
InsertInList(&L_head, 94);
InsertInList(&L_head, 12);
InsertInList(&L_head, 10);
InsertInList(&L_head, 72);
InsertInList(&L_head, 18);
InsertInList(&L_head, 142);
InsertInList(&L_head, 48);
B_Node *B_head;
listTOBinary(L_head, B_head);
cout << "The Inorder Traversal of the newly created Binary Tree is: \n";
inorder(B_head);
return 0;
}
输出
The Inorder Traversal of the newly created Binary Tree is: 45 72 142 10 48 12 18 94
时间复杂度 - O(N)，其中 N 是链表中的节点数。
空间复杂度 - O(N) 以创建新的二叉树。
在这里，我们遍历了链表并为每个链表节点创建了一个新的二叉树节点。之后，我们将当前节点附加到其父节点。程序员可以尝试将数组转换为二叉树以进行更多练习。
490 次浏览
