Извлечение поддерево из BST - Пролог

Question

Допустим, у вас есть бинарное дерево поиска:

t (73, t (31, t(5,nil,nil), nil), t (101, t (83, nil, t(97,nil,nil)), t(200,nil,nil)))

, который:

   73 
      / \ 
      31  101 
     / / \ 
      5  83 200 
        /
        97 

Мне нужно написать предикат поддерево (X1, X2, T), который примет значения 2 от дерева (X1 и X2) и найдет для них наименьший общий родительский элемент и сохранит его поддерево в T.

Итак, для примера выше, если я запрашиваю: поддерева (83,200, X).

я должен получить обратно:

t(101,t(83,nil,t(97,nil,nil)),t(200,nil,nil)) 

который:

    101 
       / \ 
       83 200 
        /
        97 

Поскольку 101 наименьшее общее значение для обоих моих чисел, я понимаю, что поддерево назад. Как я мог это сделать?

Спасибо!

Answer 1

общих шаги могут быть следующими:

1. Find пути от корня к первому элементу
2. Сделайте то же самое для второго элемента
3. Путь должен обмениваться в начале некоторых элементов. Последний общий элемент - это корень поддерева.
4. Извлеките поддерево из корня.

Надеюсь, это поможет.