Программа, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути
11.12.2023, 02:32. Показов 1608. Ответов 0
Программа, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до ближайшей вершины с заданным элементом E; которая определяет количество вхождений вершины с заданным элементом E в бинарное дерево.
| F# | 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
| open System
type BinaryTree<'T> =
| Node of 'T * BinaryTree<'T> * BinaryTree<'T>
| Leaf
let rec pathLength (tree: BinaryTree<'T>) (element: 'T) : int =
let rec pathLengthHelper (subtree: BinaryTree<'T>) (element: 'T) (currentPath: int) : int =
match subtree with
| Node(value, left, right) when value = element -> currentPath
| Node(_, left, right) -> max (pathLengthHelper left element (currentPath + 1)) (pathLengthHelper right element (currentPath + 1))
| Leaf -> Int32.MinValue
pathLengthHelper tree element 0
let rec countOccurrences (tree: BinaryTree<'T>) (element: 'T) : int =
let rec countOccurrencesHelper (subtree: BinaryTree<'T>) (element: 'T) : int =
match subtree with
| Node(value, left, right) -> (if value = element then 1 else 0) + countOccurrencesHelper left element + countOccurrencesHelper right element
| Leaf -> 0
countOccurrencesHelper tree element
// Пример использования
let binaryTree =
Node(1, Node(2, Node(4, Leaf, Leaf), Node(5, Leaf, Leaf)), Node(3, Node(6, Leaf, Leaf), Node(7, Leaf, Leaf)))
let element = 5
let length = pathLength binaryTree element
let occurrences = countOccurrences binaryTree element
printfn "Длина пути от корня до ближайшей вершины с элементом %A: %i" element length
printfn "Количество вхождений элемента %A в бинарное дерево: %i" element occurrences |
|
программа, которая строит список из всех листьев начального дерева.
| F# | 1
2
3
4
5
6
7
8
9
10
| type Tree<'a> =
| Leaf of 'a
| Node of Tree<'a> * Tree<'a>
let rec getLeaves (tree: Tree<'a>) =
match tree with
| Leaf x -> [x]
| Node (left, right) -> (getLeaves left) @ (getLeaves right)
let exampleTree = Node(Node(Leaf 1, Leaf 2), Node(Leaf 3, Leaf 4))
let leavesList = getLeaves exampleTree
printfn "Leaves: %A" leavesList |
|
новое дерево из положительных элементов старого.
| F# | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| type Tree<'T> =
| Empty
| Node of 'T * Tree<'T> * Tree<'T>
let rec filterTree predicate tree =
match tree with
| Empty -> Empty
| Node(value, left, right) ->
let filteredLeft = filterTree predicate left
let filteredRight = filterTree predicate right
if predicate value then
Node(value, filteredLeft, filteredRight)
else
Empty
let originalTree = Node(5,
Node(3,
Node(2, Empty, Empty),
Node(4, Empty, Empty)),
Node(-1,
Empty,
Node(6, Empty, Empty)))
let positiveTree = filterTree (fun x -> x > 0) originalTree
printfn "Исходное дерево: %A" originalTree
printfn "Новое дерево: %A" positiveTree |
|
Вывести значение макс элемент дерева; значение мин элемента дерева. Список из дерева.
| F# | 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
| open System
// Определение структуры дерева
type Tree =
| Leaf
| Node of int * Tree * Tree
// Функция для поиска максимального элемента в дереве
let rec findMaxValue = function
| Leaf -> failwith "Дерево пустое"
| Node(value, Leaf, Leaf) -> value
| Node(value, left, Leaf) -> max value (findMaxValue left)
| Node(value, Leaf, right) -> max value (findMaxValue right)
| Node(value, left, right) -> max (max value (findMaxValue left)) (findMaxValue right)
// Функция для поиска минимального элемента в дереве
let rec findMinValue = function
| Leaf -> failwith "Дерево пустое"
| Node(value, Leaf, Leaf) -> value
| Node(value, left, Leaf) -> min value (findMinValue left)
| Node(value, Leaf, right) -> min value (findMinValue right)
| Node(value, left, right) -> min (min value (findMinValue left)) (findMinValue right)
// Функция для формирования списка из дерева
let rec treeToList = function
| Leaf -> []
| Node(value, left, right) -> treeToList left @ [value] @ treeToList right
// Пример использования
let tree =
Node(4,
Node(2,
Node(1, Leaf, Leaf),
Node(3, Leaf, Leaf)),
Node(6,
Node(5, Leaf, Leaf),
Node(7, Leaf, Leaf)))
let maxValue = findMaxValue tree
let minValue = findMinValue tree
let list = treeToList tree
printfn "Максимальное значение в дереве: %d" maxValue
printfn "Минимальное значение в дереве: %d" minValue
printfn "Список из дерева: %A" list |
|
Сумму элементов и вершину дерева.
| F# | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| type Tree<'a> =
| Leaf
| Node of 'a * Tree<'a> * Tree<'a>
let rec sumTree (tree: Tree<int>) : int =
match tree with
| Leaf -> 0
| Node(value, left, right) -> value + sumTree left + sumTree right
let rec findRoot (tree: Tree<'a>) : 'a option =
match tree with
| Leaf -> None
| Node(value, _, _) -> Some value
// Пример использования
let tree = Node(1, Node(2, Leaf, Leaf), Node(3, Leaf, Leaf))
let sum = sumTree tree
printfn "Сумма элементов дерева: %d" sum
let root = findRoot tree
match root with
| Some value -> printfn "Вершина дерева: %A" value
| None -> printfn "Дерево пустое" |
|
Сформировать дерево и выяснить есть ли в нем число, введенное с клавиатуры
| F# | 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
| open System
type BinaryTree =
| Empty
| Node of int * BinaryTree * BinaryTree
let rec containsNumber tree number =
match tree with
| Empty -> false
| Node(value, left, right) ->
if value = number then
true
elif number < value then
containsNumber left number
else
containsNumber right number
let rec insertIntoTree tree number =
match tree with
| Empty -> Node(number, Empty, Empty)
| Node(value, left, right) ->
if number < value then
Node(value, insertIntoTree left number, right)
else
Node(value, left, insertIntoTree right number)
[<EntryPoint>]
let main args =
printfn "Введите элементы для формирования дерева (разделитель - пробел):"
let input = Console.ReadLine()
let numbers = input.Split([| ' ' |], StringSplitOptions.RemoveEmptyEntries) |> Array.map int
let mutable tree = Empty
for number in numbers do
tree <- insertIntoTree tree number
printfn "Введите число для проверки наличия в дереве:"
let searchNumber = int(Console.ReadLine())
let contains = containsNumber tree searchNumber
printfn "Число %d %s в дереве." searchNumber (if contains then "находится" else "не находится")
0 // Возвращаемое значение для функции main |
|
Сформировать дерево из случайных чисел и вывести на экран число и уровень, на котором оно находиться.
| F# | 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
| open System
// Функция случайной генерации чисел
let rnd = new Random()
// Определение структуры узла дерева
type Node = { Value: int; Left: Node option; Right: Node option }
// Функция для создания узла
let createNode value =
{ Value = value; Left = None; Right = None }
// Функция для вставки значения в дерево
let rec insertValue value node =
match node with
| None -> Some (createNode value)
| Some n ->
if value <= n.Value then
Some { n with Left = insertValue value n.Left }
else
Some { n with Right = insertValue value n.Right }
// Функция для формирования дерева
let rec generateRandomTree size node =
if size = 0 then
node
else
let value = rnd.Next(100)
let newNode = insertValue value node
generateRandomTree (size - 1) newNode
// Функция для определения уровня значения в дереве
let rec getLevel value node level =
match node with
| None -> -1
| Some n ->
if value = n.Value then
level
else if value < n.Value then
getLevel value n.Left (level + 1)
else
getLevel value n.Right (level + 1)
// Функция для вывода числа и его уровня
let printNumberAndLevel value tree =
let level = getLevel value tree 0
printfn "Число: %i, Уровень: %i" value level
// Создание дерева и вывод числа и уровня для случайного значения
let tree = generateRandomTree 10 None
let randomValue = rnd.Next(100)
printNumberAndLevel randomValue tree |
|
Дерево из случайных чисел и найти в нем количество единиц.
| F# | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| open System
type Tree =
| Leaf of int
| Node of Tree * Tree
let rec generateRandomTree (depth: int) (maxValue: int) =
if depth <= 0 then
Leaf (Random().Next(maxValue))
else
Node (generateRandomTree (depth-1) maxValue, generateRandomTree (depth-1) maxValue)
let rec countOnes (tree: Tree) =
match tree with
| Leaf value -> if value = 1 then 1 else 0
| Node (left, right) -> countOnes left + countOnes right
let randomTree = generateRandomTree 5 10
let onesCount = countOnes randomTree
printfn "Сформированное случайное дерево: %A" randomTree
printfn "Количество единиц в дереве: %d" onesCount |
|
0
|
(
