Какой забавный вопрос!
const empty =
{}
const tree = (v = null, l = empty, r = empty) =>
({ v, l, r })
Нам нужны два дерева, t1 и t2 -
t1:
3
/ \
4 5
/ \
1 2
t2:
4
/ \
1 2
Мы можем легко написать их, используя tree -
const t1 =
tree
( 3
, tree(4, tree(1), tree(2))
, tree(5)
)
const t2 =
tree(4, tree(1), tree(2))
Я думаю, у вас есть правильная идея для тестирования, если два дерева equal -
- Если оба
t1 и t2 пусты, ничего не осталось для сравнения верните true - По индукции и
t1, и t2 не пусты. Если t1 xor t2 пусто, вернуть false - По индукции ни
t1, ни t2 не пусты. Если t1.v соответствует t2.v, повторите и сравните каждое поддерево
const equal = (t1 = empty, t2 = empty) =>
t1 === empty && t2 === empty
? true // 1
: t1 === empty || t2 === empty
? false // 2
: t1.v === t2.v // 3
&& equal(t1.l, t2.l)
&& equal(t2.l, t2.r)
Мы можем написать isSubTree -
- Когда
t пусто, s является поддеревом t, если s пусто - По индукции
t не пусто. вернуть equal(t,s) или повторить t.l или повторить t.r
const isSubTree = (t = empty, s = empty) =>
t === empty
? s === empty // 1
: equal(t, s) // 2
|| isSubTree(t.l, s)
|| isSubTree(t.r, s)
Посмотрите код в действии! Проверьте результаты в своем браузере ниже -
const empty =
{}
const tree = (v = null, l = empty, r = empty) =>
({ v, l, r })
const equal = (t1 = empty, t2 = empty) =>
t1 === empty && t2 === empty
? true
: t1 === empty || t2 === empty
? false
: t1.v === t2.v
&& equal(t1.l, t2.l)
&& equal(t1.r, t2.r)
const isSubTree = (t = empty, s = empty) =>
t === empty
? s === empty
: equal(t, s)
|| isSubTree(t.l, s)
|| isSubTree(t.r, s)
const t1 =
tree
( 3
, tree(4, tree(1), tree(2))
, tree(5)
)
const t2 =
tree(4, tree(1), tree(2))
const t3 =
tree(4, tree(1), tree(9))
console.log(isSubTree(t1, t2)) // true
console.log(isSubTree(t1, t3)) // false
Я надеюсь, что этот подход показывает вам, что иногда меньше значит больше, когда дело доходит до написания программ.
boolean logi c
Этот вопрос дает хорошую возможность начать изучение логических logi c. Если вы похожи на меня, вам не нравится писать условные выражения вроде -
if (someCondition)
return true
else
return false
return someCondition ? true : false
Поскольку someCondition уже является логическим, в обоих случаях проще написать -
return someCondition
Когда мы написали equal, мы видим, что возвращаем true и false в некоторых ветвях кода. Но не совсем просто увидеть, как их можно очистить ...
const equal = (t1 = empty, t2 = empty) =>
// can we collapse the explicit bools?
t1 === empty && t2 === empty
? true // <-- explicit bool
: t1 === empty || t2 === empty
? false // <-- explicit bool
: t1.v === t2.v
&& equal(t1.l, t2.l)
&& equal(t1.r, t2.r)
Мы не хотим безрассудно гадать, какой лог c правильный. Мы подойдем к этому методично, используя таблицу истинности, чтобы получить надежный ответ -
│ p := (t1 === empty)
│ q := (t2 === empty)
┌───┬───┬──────────┬───────────┬─────────┬──────────┬──────────┬───────────┐
│ p │ q │ p 'and q │ p 'nand q │ p 'or q │ p 'nor q │ p 'xor q │ p 'xnor q │
├───┼───┼──────────┼───────────┼─────────┼──────────┼──────────┼───────────┤
│ 1 │ 1 │ 1 │ 0 │ 1 │ 0 │ 0 │ 1 │
│ 1 │ 0 │ 0 │ 1 │ 1 │ 0 │ 1 │ 0 │
│ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │ 0 │
│ 0 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │
└───┴───┴──────────┴───────────┴─────────┴──────────┴──────────┴───────────┘
Ссылаясь на нашу таблицу истинности, мы видим, что and и nor идеально описывают наши логические логические значения c -
const equal = (t1 = empty, t2 = empty) =>
//┌───┬───┬┬──────────┬──────────┐
//│ p │ q ││ p 'and q │ p 'nor q │
//├───┼───┼┼──────────┼──────────┤
t1 === empty && t2 === empty
? true //│ 1 │ 1 ││ 1 │ 0 │
: t1 === empty || t2 === empty
? false //│ 1 │ 0 ││ 0 │ 0 │
//│ 0 │ 1 ││ 0 │ 0 │
//│ 0 │ 0 ││ 0 │ 1 │
: t1.v === t2.v //└───┴───┴┴──────────┴──────────┘
&& equal(t1.l, t2.l)
&& equal(t1.r, t2.r)
Использование and соответствует двум верхним условиям и ветвям кода; nor соответствует последней ветви, в которой мы повторяемся -
const nor = (x, y) =>
!(Boolean(x) || Boolean(y))
const equal = (t1 = empty, t2 = empty) =>
//┌───┬───┬┬──────────┬──────────┐
//│ p │ q ││ p 'and q │ p 'nor q │
//├───┼───┼┼──────────┼──────────┤
nor(t1 === empty, t2 === empty) //│ 0 │ 0 ││ 0 │ 1 │
? t1.v === t2.v
&& equal(t1.l, t2.l)
&& equal(t1.r, t2.r)
: t1 === empty && t2 === empty//│ 1 │ 0 ││ 0 │ 0 │
//│ 0 │ 1 ││ 0 │ 0 │
//│ 1 │ 1 ││ 1 │ 0 │
Или простыми словами -
- Если ни одно дерево не пусто, деревья равны, если значение совпадает и поддеревья равны
- По индукции хотя бы одно дерево пусто. Деревья равны, только если оба дерева пусты.
const equal = (t1 = empty, t2 = empty) =>
nor(t1 === empty, t2 === empty)
? t1.v === t2.v // 1
&& equal(t1.l, t2.l)
&& equal(t1.r, t2.r)
: t1 === empty && t2 === empty // 2
NB, мы звоним nor перед and (&&). Это потому, что мы хотим повторяться только тогда, когда ни одно дерево не пусто. Поскольку and и nor возвращают один и тот же ответ для (p = 1, q = 0) и (p = 0, q = 1), мы можем сделать рекурсию эксклюзивной только для ветки nor, поставив ее первой.