資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
