Мне нужно создать дерево, и найти сумму которая ровняется умножению каждой вершины дерева на глубину.У меня есть два класса Node и Main. В классе Node я объявляю основные функции для роботы с деревом, в классе Main функцией readChildren заполняю дерево, но не знаю как найти глубину самого дерева (дерево не двоичное)
public class Main {
static Node<Integer> theNode;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter root value: ");
Node<Integer> root = new Node<>(Integer.parseInt(reader.readLine()));
System.out.println("Enter childs with coma separator: ");
System.out.println("For root element: ");
readChildren(root);
}
public static void readChildren(Node<Integer> child) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter children for " + child.getData() + ": ");
String children = reader.readLine();
if (children.isEmpty())
return;
String charr[] = children.split(",");
int i = 0;
for (String ch : charr) {
child.addChild(Integer.parseInt(ch));
readChildren(child.getChildren().get(i++));
}
}
}
import java.util.ArrayList;
import java.util.List;
public class Node<T> {
private List<Node<T>> children = new ArrayList<Node<T>>();
private Node<T> parent = null;
private T data = null;
public Node(T data) {
this.data = data;
}
public Node(T data, Node<T> parent) {
this.data = data;
this.parent = parent;
}
public List<Node<T>> getChildren() {
return children;
}
public void setParent(Node<T> parent) {
// parent.addChild(this);
this.parent = parent;
}
public void addChild(T data) {
Node<T> child = new Node<T>(data);
child.setParent(this);
this.children.add(child);
}
public void addChild(Node<T> child) {
child.setParent(this);
this.children.add(child);
}
public int getChildrenCount() {
return this.getChildren().size();
}
public T getData() {
return this.data;
}
public void setData(T data) {
this.data = data;
}
public boolean isRoot() {
return (this.parent == null);
}
public boolean isLeaf() {
if (this.children.size() == 0)
return true;
else
return false;
}
public void removeParent() {
this.parent = null;
}
}
ragmon
9793 золотых знака13 серебряных знаков27 бронзовых знаков
задан 14 мар 2017 в 18:47
3
написал свою функцию для поиска глубины, может кому-то понадобится
public static int getTreeHightRecurs(Node<Integer> root) {
int deep = 0;
for (Node<Integer> node :root.getChildren())
deep = Integer.max(deep, getTreeHightRecurs(node));
return deep+1;
}
ответ дан 14 мар 2017 в 21:16
mi.momi.mo
215 бронзовых знаков
Код не рабочий, я для примера привожу
public int getTreeHight(){
return getTreeHightRecurs(root);
}
private int getTreeHightRecurs(Node root){
if (root.getChildrens()=null) return 1;
List<Integer> hihgts = new LinkedList<>();
for (Node node:root.getChildrens()){
int hight = getTreeHightRecurs(node);
hihgts.add(hight);
}
return Collections.max(hihgts);
}
С java8 Stream вообще будет 2 строки, только я пока не готов его написать
ответ дан 14 мар 2017 в 19:23
TachkinTachkin
1507 бронзовых знаков
Something like this:
int countChildren(Node node)
{
if ( node == null )
return 0;
return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}
And to get the sum of the depths of every child:
int sumDepthOfAllChildren(Node node, int depth)
{
if ( node == null )
return 0; // starting to see a pattern?
return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) +
sumDepthOfAllChildren(node.getRight(), depth + 1);
}
Now for a hopefully informative explanation in case this is homework. Counting the number of nodes is quite simple. First of all, if the node isn’t a node (node == null) it returns 0. If it is a node, it first counts its self (the 1), plus the number of nodes in its left sub-tree plus the number of nodes in its right sub-tree. Another way to think of it is you visit every node via BFS, and add one to the count for every node you visit.
The Summation of depths is similar, except instead of adding just one for each node, the node adds the depth of its self. And it knows the depth of its self because its parent told it. Each node knows that the depth of it’s children are it’s own depth plus one, so when you get the depth of the left and right children of a node, you tell them their depth is the current node’s depth plus 1.
And again, if the node isn’t a node, it has no depth. So if you want the sum of the depth of all the root node’s children, you pass in the root node and the root node’s depth like so: sumDepthOfAllChildren(root, 0)
Recursion is quite useful, it’s just a very different way of thinking about things and takes practice to get accustomed to it
Напишите эффективный алгоритм для вычисления высоты бинарного дерева. Высота или глубина бинарного дерева — это общее количество ребер или узлов на самом длинном пути от корневого узла до конечного узла.
Программа должна учитывать общее количество узлов на самом длинном пути. Например, высота пустого дерева равна 0, а высота дерева только с одним узлом равна 1.
Потренируйтесь в этой проблеме
Рекурсивное решение
Идея состоит в том, чтобы обойти дерево в мода на заказ и вычислить высоту левого и правого поддерева. Высота поддерева с корнем в любом узле будет на единицу больше, чем максимальная высота его левого и правого поддеревьев. Рекурсивно примените это свойство ко всем узлам дерева восходящим образом (пост-порядок) и верните максимальную высоту поддерева с корнем в этом узле.
Алгоритм может быть реализован следующим образом на C++, Java и Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> using namespace std; // Структура данных для хранения узла бинарного дерева struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Рекурсивная функция для вычисления высоты заданного бинарного дерева int height(Node* root) { // базовый случай: пустое дерево имеет высоту 0 if (root == nullptr) { return 0; } // повторяем для левого и правого поддерева и учитываем максимальную глубину return 1 + max(height(root->left), height(root->right)); } int main() { Node* root = new Node(15); root->left = new Node(10); root->right = new Node(20); root->left->left = new Node(8); root->left->right = new Node(12); root->right->left = new Node(16); root->right->right = new Node(25); cout << “The height of the binary tree is “ << height(root); return 0; } |
Скачать Выполнить код
результат:
The height of the binary tree is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Класс для хранения узла бинарного дерева class Node { int key; Node left = null, right = null; Node(int key) { this.key = key; } } class Main { // Рекурсивная функция для вычисления высоты заданного бинарного дерева public static int height(Node root) { // базовый случай: пустое дерево имеет высоту 0 if (root == null) { return 0; } // повторяем для левого и правого поддерева и учитываем максимальную глубину return 1 + Math.max(height(root.left), height(root.right)); } public static void main(String[] args) { Node root = new Node(15); root.left = new Node(10); root.right = new Node(20); root.left.left = new Node(8); root.left.right = new Node(12); root.right.left = new Node(16); root.right.right = new Node(25); System.out.println(“The height of the binary tree is “ + height(root)); } } |
Скачать Выполнить код
результат:
The height of the binary tree is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
# Класс для хранения узла бинарного дерева. class Node: def __init__(self, key=None, left=None, right=None): self.key = key self.left = left self.right = right # Рекурсивная функция для вычисления высоты заданного бинарного дерева def height(root): # Базовый случай: пустое дерево имеет высоту 0 if root is None: return 0 # повторяется для левого и правого поддерева и учитывает максимальную глубину return 1 + max(height(root.left), height(root.right)) if __name__ == ‘__main__’: root = Node(15) root.left = Node(10) root.right = Node(20) root.left.left = Node(8) root.left.right = Node(12) root.right.left = Node(16) root.right.right = Node(25) print(‘The height of the binary tree is’, height(root)) |
Скачать Выполнить код
результат:
The height of the binary tree is 3
Временная сложность приведенного выше рекурсивного решения равна O(n), куда n это общее количество узлов в бинарном дереве. Вспомогательное пространство, необходимое программе, равно O(h) для стека вызовов, где h это высота дерева.
Итеративное решение
В итеративной версии выполните обход порядка уровней на дереве. Тогда высота дерева равна общему количеству уровней в нем. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <iostream> #include <list> using namespace std; // Структура данных для хранения узла бинарного дерева struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Итерационная функция для вычисления высоты заданного бинарного дерева // путем обхода дерева по уровням int height(Node* root) { // пустое дерево имеет высоту 0 if (root == nullptr) { return 0; } // создаем пустую queue и ставим в queue корневой узел list<Node*> queue; queue.push_back(root); Node* front = nullptr; int height = 0; // цикл до тех пор, пока queue не станет пустой while (!queue.empty()) { // вычисляем общее количество узлов на текущем уровне int size = queue.size(); // обрабатываем каждый узел текущего уровня и ставим их в queue // непустые левый и правый потомки while (size—) { front = queue.front(); queue.pop_front(); if (front->left) { queue.push_back(front->left); } if (front->right) { queue.push_back(front->right); } } // увеличиваем высоту на 1 для каждого уровня height++; } return height; } int main() { Node* root = new Node(15); root->left = new Node(10); root->right = new Node(20); root->left->left = new Node(8); root->left->right = new Node(12); root->right->left = new Node(16); root->right->right = new Node(25); cout << “The height of the binary tree is “ << height(root); return 0; } |
Скачать Выполнить код
результат:
The height of the binary tree is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
import java.util.ArrayDeque; import java.util.Queue; // Класс для хранения узла бинарного дерева class Node { int key; Node left = null, right = null; Node(int data) { this.key = data; } } class Main { // Итерационная функция для вычисления высоты заданного бинарного дерева // путем обхода дерева по уровням public static int height(Node root) { // пустое дерево имеет высоту 0 if (root == null) { return 0; } // создаем пустую queue и ставим в queue корневой узел Queue<Node> queue = new ArrayDeque<>(); queue.add(root); Node front = null; int height = 0; // цикл до тех пор, пока queue не станет пустой while (!queue.isEmpty()) { // вычисляем общее количество узлов на текущем уровне int size = queue.size(); // обрабатываем каждый узел текущего уровня и ставим их в queue // непустые левый и правый потомки while (size— > 0) { front = queue.poll(); if (front.left != null) { queue.add(front.left); } if (front.right != null) { queue.add(front.right); } } // увеличиваем высоту на 1 для каждого уровня height++; } return height; } public static void main(String[] args) { Node root = new Node(15); root.left = new Node(10); root.right = new Node(20); root.left.left = new Node(8); root.left.right = new Node(12); root.right.left = new Node(16); root.right.right = new Node(25); System.out.println(“The height of the binary tree is “ + height(root)); } } |
Скачать Выполнить код
результат:
The height of the binary tree is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
from collections import deque # Класс для хранения узла бинарного дерева. class Node: def __init__(self, data, left=None, right=None): self.key = data self.left = left self.right = right # Итерационная функция для вычисления высоты заданного бинарного дерева #, выполняя обход по порядку уровней в дереве def height(root): # Пустое дерево # имеет высоту 0 if root is None: return 0 # создает пустую queue и ставит в queue корневой узел queue = deque() queue.append(root) height = 0 # Цикл # до тех пор, пока queue не станет пустой while queue: # вычисляет общее количество узлов на текущем уровне size = len(queue) # обрабатывает каждый узел текущего уровня и ставит их в queue. # непустые левый и правый потомки while size > 0: front = queue.popleft() if front.left: queue.append(front.left) if front.right: queue.append(front.right) size = size – 1 # увеличивает высоту на 1 для каждого уровня height = height + 1 return height if __name__ == ‘__main__’: root = Node(15) root.left = Node(10) root.right = Node(20) root.left.left = Node(8) root.left.right = Node(12) root.right.left = Node(16) root.right.right = Node(25) print(‘The height of the binary tree is’, height(root)) |
Скачать Выполнить код
результат:
The height of the binary tree is 3
Временная сложность приведенного выше итеративного решения равна O(n), куда n это общее количество узлов в бинарном дереве. Вспомогательное пространство, необходимое программе, равно O(n) для структуры данных queue.
Спасибо за чтение.
Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.
Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования 🙂
Теперь давайте посмотрим, какие операции мы можем выполнять с двоичным деревом.
3.1. Вставка элементов
Первая операция, которую мы рассмотрим, – это вставка новых узлов.
Во-первых,we have to find the place where we want to add a new node in order to keep the tree sorted. Мы будем следовать этим правилам, начиная с корневого узла:
-
если значение нового узла ниже, чем значение текущего узла, мы переходим к левому дочернему элементу
-
если значение нового узла больше, чем значение текущего узла, мы переходим к правому дочернему элементу
-
когда текущий узел равенnull,, мы достигли листового узла и можем вставить новый узел в эту позицию
Сначала мы создадим рекурсивный метод для вставки:
private Node addRecursive(Node current, int value) {
if (current == null) {
return new Node(value);
}
if (value < current.value) {
current.left = addRecursive(current.left, value);
} else if (value > current.value) {
current.right = addRecursive(current.right, value);
} else {
// value already exists
return current;
}
return current;
}Затем мы создадим общедоступный метод, который запускает рекурсию с узлаroot:
public void add(int value) {
root = addRecursive(root, value);
}Теперь давайте посмотрим, как мы можем использовать этот метод для создания дерева из нашего примера:
private BinaryTree createBinaryTree() {
BinaryTree bt = new BinaryTree();
bt.add(6);
bt.add(4);
bt.add(8);
bt.add(3);
bt.add(5);
bt.add(7);
bt.add(9);
return bt;
}3.2. Поиск элемента
Давайте теперь добавим метод, чтобы проверить, содержит ли дерево определенное значение.
Как и раньше, сначала мы создадим рекурсивный метод для обхода дерева:
private boolean containsNodeRecursive(Node current, int value) {
if (current == null) {
return false;
}
if (value == current.value) {
return true;
}
return value < current.value
? containsNodeRecursive(current.left, value)
: containsNodeRecursive(current.right, value);
}Здесь мы ищем значение, сравнивая его со значением в текущем узле, а затем продолжаем в левом или правом дочернем элементе в зависимости от этого.
Затем давайте создадим общедоступный метод, который начинается сroot:
public boolean containsNode(int value) {
return containsNodeRecursive(root, value);
}Теперь давайте создадим простой тест, чтобы убедиться, что дерево действительно содержит вставленные элементы:
@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
BinaryTree bt = createBinaryTree();
assertTrue(bt.containsNode(6));
assertTrue(bt.containsNode(4));
assertFalse(bt.containsNode(1));
}Все добавленные узлы должны содержаться в дереве.
3.3. Удаление элемента
Другой распространенной операцией является удаление узла из дерева.
Во-первых, мы должны найти узел для удаления таким же образом, как мы делали раньше:
private Node deleteRecursive(Node current, int value) {
if (current == null) {
return null;
}
if (value == current.value) {
// Node to delete found
// ... code to delete the node will go here
}
if (value < current.value) {
current.left = deleteRecursive(current.left, value);
return current;
}
current.right = deleteRecursive(current.right, value);
return current;
}Как только мы найдем узел для удаления, есть 3 основных случая:
-
a node has no children – это простейший случай; нам просто нужно заменить этот узел наnull в его родительском узле
-
a node has exactly one child – в родительском узле, мы заменяем этот узел его единственным дочерним узлом.
-
a node has two children – это самый сложный случай, потому что он требует реорганизации дерева
Давайте посмотрим, как мы можем реализовать первый случай, когда узел является листовым:
if (current.left == null && current.right == null) {
return null;
}Теперь давайте продолжим случай, когда у узла есть один дочерний элемент:
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}Здесь мы возвращаем дочерний элементnon-null, чтобы его можно было назначить родительскому узлу.
Наконец, мы должны обработать случай, когда узел имеет двух детей.
Во-первых, нам нужно найти узел, который заменит удаленный узел. Мы будем использовать самый маленький узел из правого поддерева удаляемого узла:
private int findSmallestValue(Node root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}Затем мы присваиваем наименьшее значение удаляемому узлу, и после этого мы удалим его из правого поддерева:
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;Наконец, давайте создадим общедоступный метод, который начнет удаление изroot:
public void delete(int value) {
root = deleteRecursive(root, value);
}Теперь давайте проверим, что удаление работает должным образом:
@Test
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
BinaryTree bt = createBinaryTree();
assertTrue(bt.containsNode(9));
bt.delete(9);
assertFalse(bt.containsNode(9));
}1. Глубина бинарного дерева
От корневых узлов до листового узла узел (включая корни и узлы листьев), чтобы сформировать путь для образования пути, длина самого длинного пути – это глубина дерева.
2. Рекурсивная реализация Java
Если вам нужна глубина двоичного дерева, то может потребоваться глубина его левого поддерево и глубины правого поддерева, и можно использовать сам рекурсивный вызов.
public int TreeDepth(TreeNode root) {
if(root == null)//
return 0;
int left = timedepth (root.left); // ищите глубину левого поддерево
int right = trieDepth (root.richt); // ищите глубину правого поддерево
return left > right ? left +1 : right + 1;
// return trieDepth (root.left)> trieDepth (root.richt)? TreeDepth (root.left) +1: trieDepth (root.richt) +1; // Этот код может заменить приведенные выше три предложения.
}3. Версия реализации Java-не-рекурсивного
Используйте идеи пересечения последовательности слоев, чтобы получить глубину бинарного дерева (записано количество пересеченных слоев)
public int TreeDepth(TreeNode root) {
if(root == null)
return 0;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(root);
int len = 1; // Записать количество текущих слоев
int depth = 0;
while(len != 0) {
глубина ++; // каждая глубина цикла +1
int index = 0; // Записать количество узлов следующего слоя
for(int i = 0; i < len; i ++) {
TREENODE NODE = list.poll (); //
if(node.left != null) {
index++;
list.add (node.left); //
}
if(node.right != null) {
index++;
list.add (node.right); //
}
}
len = index;
}
return depth;
}