Полное бинарное дерево — это бинарное дерево, у которого все уровни, кроме последнего, полностью заполнены, а все листья последнего уровня расположены слева.
Другими словами -
Полное бинарное дерево — это бинарное дерево, в котором все узлы заполнены, кроме конечных узлов, а листовые узлы расположены сначала слева.
Теперь давайте подумаем о преобразовании массива в полное бинарное дерево —
Мы знаем, что в представлении бинарного дерева в виде массива левый дочерний элемент узла существует с индексом 2i+1, а правый дочерний элемент — с 2i+2.
Эту концепцию можно использовать для заполнения узлов и создания дерева.
Давайте попробуем понять из приведенного выше изображения -
Сначала мы пытаемся использовать первый элемент массива с индексом 0,
поэтому для индекса = 0
корень = массив[0]; // 2
root.left = массив [2*0+1] // 3
root.right = массив[2*0+2] // 6
Теперь напишем программу -
class Node {
constructor(value) {
this.data = value;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
inOrderTraversal() {
const traverse = (root) => {
if (root == null) {
return;
}
traverse(root.left);
console.log(root.data);
traverse(root.right);
}
traverse(this.root);
}
}
function createCompleteBinaryTreeFromArray(arr) {
const length = arr.length;
const binaryTree = new BinaryTree();
const traverseAndReplace = (root, i) => {
if (i < length) {
root = new Node(arr[i]);
root.left = traverseAndReplace(root.left, 2 * i + 1);
root.right = traverseAndReplace(root.right, 2 * i + 2);
}
return root;
}
binaryTree.root = traverseAndReplace(binaryTree.root, 0);
return binaryTree;
}
const result = createCompleteBinaryTreeFromArray([1, 2, 3, 4, 5, 6, 6, 6, 6]);
result.inOrderTraversal();
В методе создания мы проверяем, меньше ли индекс длины, а затем присваиваем значение корню, левому и правому краю.
