Бинарные деревья

43. Определить наличие на каком-либо из путей от корня до листа хотя бы двух узлов с одинаковым именем.

Аргументы: произвольное бинарное дерево.

?- pred(a(f(a(m,k),r),n)).
yes
?- pred(a(f(d(m,k),r),n)).
no
?-

44. Определить наличие хотя бы двух узлов с одинаковым именем на одной глубине.

Аргументы: произвольное бинарное дерево.

?- pred(s(f(b(m,k),a),n(b,g))).
yes
?- pred(s(f(b(m,k),a),n(t,g))).
no
?-

45. Определить наличие двух одинаковых путей от корня до листа.

Аргументы: произвольное бинарное дерево.

?- pred(s(f(b(m,k),a),f(a,g))).
yes
?- pred(s(f(y(m,k),a),f(t,g))).
no
?-

46. Расширить синтаксис языка Пролог, введя операции (см. встроенный предикат op/3) над комплексными числами. Следует использовать имя «isс» для операции извлечения результата и стандартные «+, -, *, /, ^» для арифметических операций.

Аргументы: арифметическое выражение;
свободная переменная.

?- X isс (1.6, 4.5) + (2.8, 7.1).
X = (4.4, 11.6)
yes
?-

47. Определить глубину дерева.

Аргументы: произвольное бинарное дерево;
глубина дерева.

?- pred(s(f(b(m,k),a),f(a,g)),X).
X = 4
yes
?-

48. Определить, являются ли два заданных дерева равными с точностью до перестановки левого и правого поддерева в каждом узле.

Аргументы: первое дерево;
второе дерево.

?- pred(s(t(b(m,k),a),f(a,g)), s(t(b(k,m),a),f(g,a))).
yes
?- pred(s(t(b(m,k),a),f(a,g)), s(t(a,b(k,m)),f(g,a))).
yes
?-

49. Собрать все узлы в список.

Аргументы: произвольное бинарное дерево;
список узлов.

?- pred(s(f(b(m,k),a),f(a,g)),X).
X = [s,f,b,m,k,a,f,a,g]
yes
?-

50. В каждом узле дерева поменять при необходимости поддеревья местами так, чтобы в результирующем дереве в каждом узле выполнялось требование – количество узлов в левом поддереве не больше, чем в правом.

Аргументы: произвольное бинарное дерево;
результирующее дерево.

?- pred(s(f(b(m,k),a),t(a,g)),X).
X = s(t(a,g),f(a,b(m,k)))
yes
?-

51. Найти максимум количества узлов лежащих на одной глубине.

Аргументы: произвольное бинарное дерево;
количество узлов.

?- pred(s(f(b(m,k),a),t(r,w)),X).
X = 4
yes
?-

52. Собрать в список имена всех узлов дерева, лежащих на заданной глубине.

Аргументы: произвольное бинарное дерево;
необходимая глубина;
список узлов.

?- pred(s(f(b(m,k),a),t(a,g)),1,X).
X = [s]
yes
?- pred(s(f(b(m,k),a),t(a,g)),3,X).
X = [b,a,a,g]
yes
?- pred(s(f(b(m,k),a),t(a,g)),5,X).
X = []
yes
?-

53. Обрезать дерево на заданной глубине.

Аргументы: произвольное бинарное дерево;
необходимая глубина;
результирующее дерево.

?- pred(s(f(b(m,k),a),t(a,g)),2,X).
X = s(f,t)
yes
?- pred(s(f(b(m,k),a),t(a,g)),3,X).
X = s(f(b,a),t(a,g))
yes
?-

54. Произвести следующую процедуру над деревом, начиная обработку с корня: в текущем узле с заданной вероятностью принимается решение об усечении дерева в этом узле (узел становится листом).

Аргументы: произвольное бинарное дерево;
вероятность усечения;
результирующее дерево.

?- pred(s(f(b(m,k),a),t(a,g)),0.5,X).
X = s(f,t(a,g))
yes
?- pred(s(f(b(m,k),a),t(a,g)),0.5,X).
X = s(f(b,a),t)
yes
?- pred(s(f(b(m,k),a),t(a,g)),0.5,X).
X = s
yes
?-

55. Заданный узел в дереве сделать корнем дерева с той же связностью узлов, что и в исходном дереве. Результирующее дерево не является бинарным.

Аргументы: произвольное бинарное дерево;
имя узла;
результирующее дерево.

?- pred(s(f(b(m,k),w),t(a,g)),s,X).
X = s(f(b(m,k),w),t(a,g))
yes
?- pred(s(f(b(m,k),w),t(a,g)),f,X).
X = f(b(m,k),w,s(t(a,g)))
yes
?- pred(s(f(b(m,k),w),t(a,g)),a,X).
X = a(t(s(f(b(m,k),w)),g)
yes
?-

56. Подсчитать количество узлов дерева, лежащих на заданной глубине.

Аргументы: произвольное бинарное дерево;
необходимая глубина;
количество узлов.

?- pred(s(f(b(m,k),a),t(a,w)),1,X).
X = 1
yes
?- pred(s(f(b(m,k),a),t(a,w)),3,X).
X = 4
yes
?- pred(s(f(b(m,k),a),t(a,w)),4,X).
X = 2
yes
?-

57. Произвести обработку дерева в каждом узле по следующему правилу. Если узел имеет заданное имя, то все его дочерние узлы должны стать дочерними узлами его родительского узла, а сам этот узел удаляется из дерева.

Аргументы: произвольное бинарное дерево;
имя узла;
результирующее дерево.

?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g)),b,X).
X = s(f(u(i,o),v,k,a),t(g))
yes
?-

58. Подсчитать количество узлов с заданным именем.

Аргументы: произвольное бинарное дерево;
имя узла;
количество узлов.

?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g)),b,X).
X = 3
yes
?-

59. Определить путь между двумя заданными узлами.

Аргументы: произвольное бинарное дерево;
имя первого узла;
имя второго узла;
путь (список).

?- pred(s(f(w(b(u(i,o),v),k),a),t(r,g)),w,r,X).
X = [w,f,s,t,r]
yes
?- pred(s(f(w(b(u(i,o),v),k),a),t(r,g)),i,o,X).
X = [i,u,o]
yes
?-

60. Переименовать все узлы, имеющие заданное имя.

Аргументы: произвольное бинарное дерево;
старое имя узла;
новое имя узла;
результирующее дерево.

?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g)),b,r,X).
X = s(f(r(r(u(i,o),v),k),a),t(r,g))
yes
?-

61. Найти все поддеревья заданного дерева.

Аргументы: произвольное бинарное дерево;
поддерево.

?- pred(a(f(a(m,k),r),n(i,o)),X).
X = a(f(a(m,k),r),n(i,o)) -> ;
X = f(a(m,k),r) -> ;
X = a(m,k) -> ;
X = m -> ;
X = k -> ;
X = r -> ;
X = n(i,o) -> ;
X = i -> ;
X = o -> ;
no
?-

62. Найти все пути в дереве от корня до его листьев.

Аргументы: произвольное бинарное дерево;
путь (список).

?- pred(a(f(a(m,k),r),n(i,o)),X).
X = [a,f,a,m] -> ;
X = [a,f,a,k] -> ;
X = [a,f,r] -> ;
X = [a,n,i] -> ;
X = [a,n,o] -> ;
no
?-

63. Найти все пути от корня до его листьев, лежащих на максимальной глубине.

Аргументы: произвольное бинарное дерево;
путь (список).

?- pred(a(f(a(m,k),r),n(i,o)),X).
X = [a,f,a,m] -> ;
X = [a,f,a,k] -> ;
no
?-

64. Найти все поддеревья, имеющие глубину не больше заданной.

Аргументы: произвольное бинарное дерево;
максимальная глубина;
поддерево.

?- pred(a(f(a(m,k),r),n(i,o)),2,X).
X = a(m,k) -> ;
X = m -> ;
X = k -> ;
X = r -> ;
X = n(i,o) -> ;
X = i -> ;
X = o -> ;
no
?-

65. Выполнить перебор листьев в порядке убывания их глубины.

Аргументы: произвольное бинарное дерево;
лист дерева.

?- pred(a(f(a(m,k),r),n(i(d,e),o)),X).
X = m -> ;
X = k -> ;
X = d -> ;
X = e -> ;
X = r -> ;
X = o -> ;
no
?-

66. Произвести приведение полинома.

Аргументы: исходный полином;
результирующий полином.

?- pred(2+6*x^3-7*x^2-4+x^3+6*x^2,X).
X = -2-x^2+7*x^3
yes
?-

67. Произвести символьное дифференцирование полинома, который задается структурой вида: a+b*x+c*x^2+d*x^3+…

Аргументы: исходный полином;
результирующий полином.

?- pred(2+6*x-7*x^3,X).
X = 6-21*x^2
yes
?-

68. Произвести деление полиномов. Исходные полиномы задаются структурами вида: a+b*x+c*x^2+d*x^3+…

Аргументы: первый полином;
второй полином;
результирующий полином, остаток от деления.

?- pred(2+6*x-7*x^3,1+x,X,Y).
X = -7*x^2+7*x-1
Y = 3
yes
?-

69. Расширить синтаксис языка Пролог, введя операции (см. встроенный предикат op/3) над множествами (списки). Следует использовать следующие имена операций: «iss» – операция извлечения результата; «+» – операция объединения; «*» – операция пересечения; «-» – операция вычитания.

Аргументы: арифметическое выражение (в арифметике множеств);
свободная переменная.

?- X iss [a,s,d,f] * [d,g,f] + [p,f].
X = [d,f,p]
yes
?-

70. Расширить синтаксис языка Пролог, введя операции (см. встроенный предикат op/3) модульной арифметики (арифметики вычетов, см. приложение В). Следует использовать имя «ism» для операции извлечения результата и стандартные «+, -, *, /» – для арифметических операций. Для хранения модуля, по которому производятся вычисления, необходимо использовать факт ism/1. В качестве модуля предполагается использовать только простые числа.

Аргументы: арифметическое выражение;
свободная переменная.

?- ism(X).
X = 3
yes
?- X ism (24+38)/2.
X = 1
yes
?-

71. Произвести перестановку поддеревьев в каждом узле дерева.

Аргументы: произвольное бинарное дерево;
результирующее дерево.

?- pred(s(f(b(m,k),a),f(a,g)),X).
X = s(f(g,a),f(a,b(m,k)))
yes
?-

Произвольные структуры (деревья)

72. Определить наличие на каком-либо из путей от корня до листа хотя бы двух узлов с одинаковым именем.

Аргументы: произвольное дерево.

?- pred(a(f(i(m,k),r,a(t)),n)).
yes
?- pred(a(f(i(m,k),r,o(t)),n)).
no
?-

73. Определить наличие хотя бы двух узлов с одинаковым именем на одной глубине.

Аргументы: произвольное дерево.

?- pred(s(f(b(m,k),a),n(b,g),r(u))).
yes
?- pred(s(f(b(m,k),a),n(t,g),r(u))).
no
?-

74. Определить наличие двух одинаковых путей от корня до листа.

Аргументы: произвольное дерево.

?- pred(s(f(b(m,k),a),f(a,g),n(h))).
yes
?- pred(s(f(y(m,k),a),f(t,g),n(h))).
no
?-

75. Определить глубину дерева.

Аргументы: произвольное дерево;
глубина дерева.

?- pred(s(f(b(m(i),k),a),f(a,g),h(y)),X).
X = 5
yes
?-

76. Определить, являются ли два заданных дерева равными с точностью до перестановки поддеревьев в каждом узле.

Аргументы: первое дерево;
второе дерево.

?- pred(s(t(b(m,k),a),f(a,g)), s(t(b(w,k,m),a),f(g))).
yes
?- pred(s(t(b(m,k),a),f(a,g)), s(t(a,b(k,m,w)),f(g))).
yes
?-

77. Собрать все узлы в список.

Аргументы: произвольное дерево;
список узлов.

?- pred(s(f(b(m,k,n),a(r)),f(a,g)),X).
X = [s,f,b,m,k,n,a,f,a,r,g]
yes
?-

78. Найти максимум количества узлов, лежащих на одной глубине.

Аргументы: произвольное дерево;
количество узлов.

?- pred(s(f(b(m,k(e),n),a),t(r,w)),X).
X = 4
yes
?-

79. Обрезать дерево на заданной глубине.

Аргументы: произвольное дерево;
необходимая глубина;
результирующее дерево.

?- pred(s(f(b(m,k),a),t(a,g),j(u)),2,X).
X = s(f,t,j)
yes
?- pred(s(f(b(m,k),a),t(a,g),j(u)),3,X).
X = s(f(b,a),t(a,g),j(u))
yes
?-

80. Собрать в список имена всех узлов дерева, лежащих на заданной глубине.

Аргументы: произвольное дерево;
необходимая глубина;
список узлов.

?- pred(s(f(b(m,k),a),t(a,g),j(u)),1,X).
X = [s]
yes
?- pred(s(f(b(m,k),a),t(a,g),j(u)),3,X).
X = [b,a,a,g,u]
yes
?- pred(s(f(b(m,k),a),t(a,g),j(u)),5,X).
X = []
yes
?-

81. Произвести следующую процедуру над деревом, начиная обработку с корня: в текущем узле с заданной вероятностью принимается решение об усечении дерева в этом узле (узел становится листом).

Аргументы: произвольное дерево;
вероятность усечения;
результирующее дерево.

?- pred(s(f(b(m,k),a),t(a)),0.5,X).
X = s(f,t(a))
yes
?- pred(s(f(b(m,k),a),t(a)),0.5,X).
X = s(f(b,a),t)
yes
?- pred(s(f(b(m,k),a),t(a)),0.5,X).
X = s
yes
?-

82. Найти в дереве все поддеревья, являющиеся бинарными.

Аргументы: произвольное дерево;
поддерево.

?- pred(a(f(a(m,k(v)),r),n(i(d,e,z(q,w)),o)),X).
X = z(q,w) -> ;
no
?-

83. Сделать в дереве заданный узел корнем дерева с той же связностью узлов, что и в исходном дереве.

Аргументы: произвольное дерево;
имя узла;
результирующее дерево.

?- pred(s(f(b(m,k),w),t(a)),s,X).
X = s(f(b(m,k),w),t(a))
yes
?- pred(s(f(b(m,k),w),t(a)),f,X).
X = f(b(m,k),w,s(t(a)))
yes
?- pred(s(f(b(m,k),w),t(a)),a,X).
X = a(t(s(f(b(m,k),w)))
yes
?-

84. Подсчитать количество узлов дерева, лежащих на заданной глубине.

Аргументы: произвольное дерево;
необходимая глубина;
количество узлов.

?- pred(s(f(b(m,k),a),t(a)),1,X).
X = 1
yes
?- pred(s(f(b(m,k),a),t(a)),3,X).
X = 3
yes
?- pred(s(f(b(m,k),a),t(a)),4,X).
X = 2
yes
?-

85. Подсчитать количество узлов с заданным именем.

Аргументы: произвольное дерево;
имя узла;
количество узлов.

?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g,b(i))),b,X).
X = 4
yes
?-

86. Произвести обработку дерева в каждом узле по следующему правилу. Если узел имеет заданное имя, то все его дочерние узлы должны стать дочерними узлами его родительского узла, а сам этот узел удаляется из дерева.

Аргументы: произвольное дерево;
имя узла;
результирующее дерево.

?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g),b),b,X).
X = s(f(u(i,o),v,k,a),t(g))
yes
?-

87. Определить путь между двумя заданными узлами.

Аргументы: произвольное дерево;
имя первого узла:
имя второго узла;
путь (список).

?- pred(s(f(w(b(u(i,o,d),v),k),a),t(r(u),g),m),w,r,X).
X = [w,f,s,t,r]
yes
?- pred(s(f(w(b(u(i,o,d),v),k),a),t(r(u),g),m),i,d,X).
X = [i,u,d]
yes
?-

88. Переименовать все узлы, имеющие заданное имя.

Аргументы: произвольное дерево;
старое имя узла;
новое имя узла;
результирующее дерево.

?- pred(s(f(b(b(u(i,o),v),k),a),t(b(e),g),b),b,r,X).
X = s(f(r(r(u(i,o),v),k),a),t(r(e),g),r)
yes
?-

89. Найти все поддеревья.

Аргументы: произвольное дерево;
поддерево.

?- pred(a(f(a(m,k,v),r),n(i)),X).
X = a(f(a(m,k,v),r),n(i)) -> ;
X = f(a(m,k,v),r) -> ;
X = a(m,k,v) -> ;
X = m -> ;
X = k -> ;
X = v -> ;
X = r -> ;
X = n(i) -> ;
X = i -> ;
no
?-

90. Найти в дереве все пути от корня до его листьев.

Аргументы: произвольное дерево;
путь (список).

?- pred(a(f(a(m,k),r),n(i,o,v(x))),X).
X = [a,f,a,m] -> ;
X = [a,f,a,k] -> ;
X = [a,f,r] -> ;
X = [a,n,i] -> ;
X = [a,n,o] -> ;
X = [a,n,v,x] -> ;
no
?-

91. Найти в дереве все пути от корня до его листьев, лежащих на максимальной глубине.

Аргументы: произвольное дерево;
путь (список).

?- pred(a(f(a(m,k,v),r),n(i,o)),X).
X = [a,f,a,m] -> ;
X = [a,f,a,k] -> ;
X = [a,f,a,v] -> ;
no
?-

92. Найти в дереве все поддеревья, имеющие глубину не больше заданной.

Аргументы: произвольное дерево;
максимальная глубина;
поддерево.

?- pred(a(f(a(m,k),r,v(g)),n(i,o)),2,X).
X = a(m,k) -> ;
X = m -> ;
X = k -> ;
X = r -> ;
X = v(g) -> ;
X = g -> ;
X = n(i,o) -> ;
X = i -> ;
X = o -> ;
no
?-

93. Выполнить перебор листьев в порядке убывания их глубины.

Аргументы: произвольное дерево;
лист дерева.

?- pred(a(f(a(m,k(v)),r),n(i(d,e,z),o)),X).
X = v -> ;
X = m -> ;
X = k -> ;
X = d -> ;
X = e -> ;
X = z -> ;
X = r -> ;
X = o -> ;
no
?-

94. Найти узел, имеющий максимальное количество потомков.

Аргументы: произвольное дерево;
узел дерева.

?- pred(a(f(a(m,k(v)),r),n(i(d,e,z(q,w,t)),o)),X).
X = i -> ;
X = z -> ;
no
?-

95. Составить описание каждого узла дерева (потомки нумеруются слева направо).

Аргументы: произвольное дерево;
описание узла (атом).

?- pred(a(f(a(m,k(v)),r),n(i(d,e,z)),o),X).
X = a -> ;
X = 1:f -> ;
X = 1:1:a -> ;
X = 1:1:1:m -> ;
X = 1:1:2:k -> ;
X = 1:1:2:1:v -> ;
X = 1:2:r -> ;
X = 2:n -> ;
X = 2:1:i -> ;
X = 2:1:1:d -> ;
X = 2:1:2:e -> ;
X = 2:1:3:z -> ;
X = 3:o -> ;
no
?-

96. Дана строка, которая с помощью предиката string_term/2 (см. пример) корректно преобразуется в терм. Предполагается, что строка может преобразовываться в структуру любой арности, содержащую свободные переменные. Собрать из исходной строки в список имена свободных переменных.

Аргументы: исходная строка;
список имен переменных.

?- string_term(’r(T,m(T,K))’,B).
B = r(_70,m(_70,_84))
yes
?- pred(’r(T,m(T,K))’,X).
X = [’T’,’K’]
yes
?-

97. Сформировать графическое представление дерева в виде строки, используя символы псевдографики (см. приложение В).

Аргументы: произвольное дерево;
строка.

?- pred(a(f(a(m,k(v)),r),n(i(d,e,z)),o),X).
X =
a
├─f
│ ├─a
│ │ ├─m
│ │ └─k
│ │ └─v
│ └─r
├─n
│ └─i
│ ├─d
│ ├─e
│ └─z
└─o
yes
?-