В порядке обхода для этой реализации BTree? - PullRequest
Новая
       9

В порядке обхода для этой реализации BTree?

0 голосов
/ 26 августа 2018

Новый ученик в скале.У меня есть эти базовые классы для всех узлов и BTree 

abstract sealed class Node[T](implicit val ord : Ordering[T])

abstract sealed class BTree[T](implicit ord : Ordering[T])
extends Node[T] {
def size : Int
def depth : Int

И вот базовые случаи: 

object BTree {
//empty node
final case class EmptyNode[T]()(implicit ord : Ordering[T])
  extends BTree[T] {
val size : Int = 0
val depth : Int = 0
}
//node with 1 child
final case class OneNode[T](t : BTree[T])(implicit ord : Ordering[T])
  extends Node[T] {
val size : Int = t.size
val depth : Int = t.depth + 1
}
//node with 2 children
final case class TwoNode[T](t1 : BTree[T], u1 : T, t2 : BTree[T])
                      (implicit ord : Ordering[T]) extends BTree[T] {
val size : Int = t1.size + t2.size + 1
val depth : Int = max(t1.depth, t2.depth) + 1
}

И они продолжают шаблон для ThreeNode и FourNode

Теперь в классе BTree мне нужно реализовать функцию In Order, которая возвращает список отсортированных записей.

// Return List of values sorted alphabetically/smallest to largest
def inOrder() : List[T] =

Может кто-нибудь помочь в том, как это реализовать?Я думаю внутри функции inOrder, у меня есть другая функция, которая вызывается рекурсивно.Но я не знаю, что делать со списком.Я добавляю к нему перед каждым рекурсивным вызовом?

Любая помощь приветствуется

Ответы [ 2 ]

0 голосов
/ 26 августа 2018

Я не совсем понимаю цель ваших структур. Я ожидаю, что узел B-Tree будет выглядеть примерно так: 

case class Node[T](smaller: Seq[Node[T]] = Nil, data: Seq[([T], Seq[Node[T]])] = Nil) {
  def inOrder: Seq[T] = smaller.flatMap(_.inOrder) ++ 
    data.flatMap { case (value, children) => 
      children.flatMap(_.inOrder) :+ value
    } 
}

Это предполагает, что «потомки» всегда «вправо» от соответствующих данных (таким образом, необходимо smaller сохранить поддерево слева от всего остального на странице.

0 голосов
/ 26 августа 2018

Попытка сортировки значений при чтении их из несортированного дерева будет излишне сложной.

Итак, у вас есть два варианта:

1) Считать все значения из дерева в List, а затем отсортировать List

2) Сохраняйте дерево отсортированным по мере его построения, чтобы для каждого узла все значения в ветви left были < значением узла, а все значения в ветви right были >=. значение узла. Затем вы можете получить отсортированный список, обходя дерево слева направо в порядке глубины. В этом случае вы бы никогда не использовали ThreeNode или FourNode, которые (как я указывал в предыдущем ответе) значительно усложняют ситуацию.

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

...