완전한 바이너리의 연결 목록 표현이 주어지면 나무. 연결 목록은 레벨 순서 순회 나무의. 완전한 이진 트리를 구성하는 알고리즘을 작성하십시오. 연결 목록 대표.
차례
예
입력
1-> 2-> 3-> 4-> 5
산출
순회 순회
4 2 5 1 3
완전한 이진 트리 생성을위한 알고리즘
완전한 이진 트리는 마지막 수준을 제외하고 모든 수준이 완전히 채워진 이진 트리이며 마지막 수준의 모든 노드는 가능한 한 남아 있습니다. 또한 완전한 트리가 배열을 통해 표현 될 때 배열의 인덱스 i에있는 노드는 인덱스 (2 * i + 1)에 왼쪽 자식이 있고 인덱스 (2 * i + 2)에 오른쪽 자식이 있습니다. 링크드리스트 표현에서 같은 것을 시각화 할 수 있습니다.
따라서 인덱스 0에있는 노드의 자식은 인덱스 1과 2에 있고, 인덱스 1에있는 노드의 자식은 인덱스 3과 4에있는 식입니다.
연결 목록 표현을 트리로 변환하는 아이디어는 연결 목록의 첫 번째 노드가 항상 트리의 루트라는 것입니다. 그래서 우리는 큐에 루트를 밀어 넣고, 트리에서 BFS를 수행하고 동시에 연결 목록을 트래버스하여 트리로 변환합니다. 트리의 모든 노드에 대해 링크 된 목록의 두 노드를 탐색합니다. 하나는 왼쪽 자식 용이고 다른 하나는 오른쪽 자식 용입니다.
- 대기열을 만듭니다.
- 연결 목록의 헤드를 대기열로 푸시합니다.
- 연결 목록의 끝에 도달하지 않은 동안 4 단계를 반복하십시오.
- 큐에서 노드를 제거하고 부모가되도록합니다. 목록에서 순회하면 첫 번째 노드는 부모의 왼쪽 자식이고 두 번째 노드는 부모의 오른쪽 자식입니다. 또한 왼쪽 및 오른쪽 자식을 대기열에 넣습니다.
완전한 이진 트리 구성을위한 JAVA 코드
import java.util.LinkedList;
import java.util.Queue;
public class ConstructCompleteBinaryTreeFromItsLinkedListRepresentation {
// class representing node of a linked list
static class ListNode {
int data;
ListNode next;
public ListNode(int data) {
this.data = data;
}
}
// class representing node of a binary tree
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int data) {
this.data = data;
}
}
// function to print inorder traversal of a tree
private static void inorder(TreeNode root) {
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
private static void constructCompleteBinaryTree(ListNode head) {
if (head == null) {
return;
}
// initialize root of the tree as head of linked list
TreeNode root = new TreeNode(head.data);
// create a queue
Queue<TreeNode> q = new LinkedList<>();
// push the root of the tree to the queue
q.add(root);
while (head != null) {
// remove an element from the queue
TreeNode parent = q.poll();
// traverse in linked list
head = head.next;
if (head != null) {
// this node of linked list is the left child of parent
TreeNode leftChild = new TreeNode(head.data);
parent.left = leftChild;
// add left child to the queue
q.add(leftChild);
// traverse in linked list
head = head.next;
if (head != null) {
// this node of the linked list is the right child of parent
TreeNode rightChild = new TreeNode(head.data);
parent.right = rightChild;
// add right child to the queue
q.add(rightChild);
}
}
}
// print inorder traversal of the tree
System.out.println("Inorder Traversal");
inorder(root);
System.out.println();
}
public static void main(String[] args) {
// Example
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
constructCompleteBinaryTree(head);
}
}
Inorder Traversal 4 2 5 1 3
완전한 이진 트리 생성을위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
// class representing node of a linked list
class ListNode {
public:
int data;
ListNode *next;
ListNode(int d) {
data = d;
next = NULL;
}
};
// class representing node of a binary tree
class TreeNode {
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int d) {
data = d;
left = right = NULL;
}
};
// function to print inorder traversal of a tree
void inorder(TreeNode *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
void constructCompleteBinaryTree(ListNode *head) {
if (head == NULL) {
return;
}
// initialize root of the tree as head of linked list
TreeNode *root = new TreeNode(head->data);
// create a queue
queue<TreeNode *> q;
// push the root of the tree to the queue
q.push(root);
while (head != NULL) {
// remove an element from the queue
TreeNode *parent = q.front();
q.pop();
// traverse in linked list
head = head->next;
if (head != NULL) {
// this node of linked list is the left child of parent
TreeNode *leftChild = new TreeNode(head->data);
parent->left = leftChild;
// add left child to the queue
q.push(leftChild);
// traverse in linked list
head = head->next;
if (head != NULL) {
// this node of the linked list is the right child of parent
TreeNode *rightChild = new TreeNode(head->data);
parent->right = rightChild;
// add right child to the queue
q.push(rightChild);
}
}
}
// print inorder traversal of the tree
cout<<"Inorder Traversal"<<endl;
inorder(root);
cout<<endl;
}
int main() {
ListNode *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
constructCompleteBinaryTree(head);
return 0;
}
Inorder Traversal 4 2 5 1 3
복잡성 분석
시간 복잡성 = O (N)
공간 복잡성 = O (N)
여기서 n은 연결 목록의 요소 수입니다.
