f # доступ к корневому элементу дерева - PullRequest
Новая
       11

f # доступ к корневому элементу дерева

1 голос
/ 28 апреля 2011

У меня есть каноническое дерево в F #, то есть путем объявления 

type binaryTree = 
    | Leaf
    | Node of binaryTree * float * binaryTree

и последующего использования рекурсивной функции для создания дерева 

let rec makeTree tree element = 
    match element, tree with
        | x, Leaf -> Node(Leaf,x,Leaf)
        | x, Node(l,y,r) -> Node(l,y, (makeTree r x))

Это нормально.Теперь я хочу отсортировать дерево так, чтобы на каждом узле значение узла было меньше, чем значение всех его дочерних элементов.Я могу представить, как это сделать.Тем не менее, я хочу затем взять первый элемент дерева.То есть я хочу рассматривать дерево как очередь.Единственные примеры, которые я видел с деревьями, используют функции высшего порядка, чтобы что-то делать с деревом, но это кажется пустой тратой, когда я уже отсортировал это.

Как я могу получить доступ к корневому узлу этого дерева?

Ответы [ 2 ]

2 голосов
/ 28 апреля 2011

Как насчет этого: 

let rootValue (Node(_,v,_)) = v

Это вызовет исключение, если дерево пустое.В качестве альтернативы: 

let tryGetRootValue = function
| Node(_,v,_) -> Some v
| _ -> None

Это всегда будет успешным, но вернет float option вместо float.

2 голосов
/ 28 апреля 2011

Вопрос немного неясен.Насколько я понимаю, у вас будет дерево, в котором значение узла меньше значения его потомков.(Это можно реализовать, отсортировав дерево или написав другую функцию, которая создает его так, что это правда.)

Чтобы реализовать функцию, которая принимает первый (самый маленький) элемент дерева, вам необходимоудалите корень (который является самым маленьким), а затем объедините два дерева, которые вы получите.Это можно сделать, взяв в качестве нового корня меньший из двух корней и рекурсивно объединив новые деревья, которые вы получите.Следующий фрагмент должен сделать трюк: 

let rec merge t1 t2 = 
  match t1, t2 with
  | Leaf, t | t, Leaf -> t // Merging a tree and a leaf gives the tree
  | (Node(ll, x1, lr) as t1), (Node(rl, x2, rr) as t2) ->
      // When merging two trees, take the smaller root as a new root
      // This gives you three new trees, so two of them must be recursively merged
      if x1 < x2 then Node(merge ll lr, x1, t2)
      else Node(t1, x2, merge rl rr)

let rec tryTake tree = 
  match tree with
  | Leaf -> None
  | Node(t1, y, t2) -> Some(y, merge t1 t2)
...