Рекурсивный поиск узла в дереве

Question

Я хочу построить дерево, используя только две структуры: Node и Tree, а затем рекурсивно искать целевой узел из дерева. Если цель найдена, верните true, иначе верните false.

Задача для меня здесь заключается в том, как рекурсивно вызвать функцию find, поскольку она определена только на Tree не Node.

pub struct Node<T> { 
    value: T, 
    left: Option<Box<Node<T>>>, 
    right: Option<Box<Node<T>>>, 
} 

pub struct Tree<T> { 
    root: Option<Box<Node<T>>>, 
} 

impl<T: Ord> Tree<T> { 
    /// Creates an empty tree 
    pub fn new() -> Self { 
     Tree { root: None } 
    } 

    // search the tree 
    pub fn find(&self, key: &T) -> bool { 
     let root_node = &self.root; // root is Option 

     match *root_node { 
      Some(ref node) => { 

       if node.value == *key { 
        return true; 
       } 

       let target_node = if *key < node.value { 
        &node.left 
       } else { 
        &node.right 
       }; 

       match *target_node { 
        Some(sub_node) => sub_node.find(key), 
        None => { 
         return false; 
        } 
       } 
      } 
      None => return false, 
     } 
    } 
} 

fn main() { 
    let mut mytree: Tree<i32> = Tree::new(); 

    let node1 = Node { 
     value: 100, 
     left: None, 
     right: None, 
    }; 
    let boxed_node1 = Some(Box::new(node1)); 

    let root = Node { 
     value: 200, 
     left: boxed_node1, 
     right: None, 
    }; 
    let boxed_root = Some(Box::new(root)); 
    let mytree = Tree { root: boxed_root }; 

    let res = mytree.find(&100); 
} 

текущий код сообщает об ошибке:

error: no method named `find` found for type `Box<Node<T>>` in the current scope 
    --> src/main.rs:36:48 
    | 
36 |      Some(sub_node) => sub_node.find(key), 
    |            ^^^^ 
    | 
    = note: the method `find` exists but the following trait bounds were not satisfied: `Node<T> : std::iter::Iterator` 
    = help: items from traits can only be used if the trait is implemented and in scope; the following traits define an item `find`, perhaps you need to implement one of them: 
    = help: candidate #1: `std::iter::Iterator` 
    = help: candidate #2: `core::str::StrExt` 

Я понимаю, что find реализован только на Tree, так что это ошибка, но я не думаю, что это эффективно реализовать find на оба Tree и Node. Любой намек на это?

Answer 1

Вы должны переместить большинство реализации в Node типа, то оставьте только небольшой прокладка в Tree:

impl<T: Ord> Tree<T> { 
    pub fn find(&self, key: &T) -> bool { 
     self.root.as_ref().map(|n| n.find(key)).unwrap_or(false) 
    } 
} 

impl<T: Ord> Node<T> { 
    // search the tree 
    pub fn find(&self, key: &T) -> bool { 
     if self.value == *key { 
      return true; 
     } 

     let target_node = if *key < self.value { 
      &self.left 
     } else { 
      &self.right 
     }; 

     target_node.as_ref().map(|n| n.find(key)).unwrap_or(false) 
    } 
} 

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

pub fn find(&self, key: &T) -> bool { 
    use ::std::cmp::Ordering::*; 

    match self.value.cmp(key) { 
     Equal => true, 
     Less => self.left.as_ref().map(|n| n.find(key)).unwrap_or(false), 
     Greater => self.right.as_ref().map(|n| n.find(key)).unwrap_or(false), 
    } 
} 

Или

pub fn find(&self, key: &T) -> bool { 
    use ::std::cmp::Ordering::*; 

    let child = match self.value.cmp(key) { 
     Equal => return true, 
     Less => self.left.as_ref(), 
     Greater => self.right.as_ref(), 
    }; 

    child.map(|n| n.find(key)).unwrap_or(false) 
} 

I found it is hard to understand target_node.as_ref().map(|n| n.find(key)).unwrap_or(false) . I just started to learn the iterator. Is that possible to explain the long expression step by step?

Просто следуйте подписи типа каждой функции:

1. self является &Node<T>
2. &self.left/&self.right/target_node являются &Option<Box<Node<T>>>
3. Option::as_ref преобразует &Option<T> в Option<&T>. Теперь у нас есть Option<&Box<Node<T>>>.
4. Option::map применяет функцию (которая может изменить содержащийся тип) к опции, если она равна Some, в противном случае она оставляет ее None.
   1. Функция мы применяем это Node::find, который принимает &Node<T> и возвращает bool.
   2. Box<T> инвентарь Deref поэтому любые методы на T появляются на Box<T>.
   3. Automatic dereferencing позволяет обрабатывать &Box<T> как Box<T>.
   4. Теперь у нас есть Option<bool>
5. Option::unwrap_or возвращает значение, содержащееся, если есть один, в противном случае значения запасного варианта при условии. Конечный тип: bool.

Нельзя использовать черту Iterator. И Iterator, и Option имеют метод map. Если вас интересует тот факт, что они имеют одно и то же имя и делают подобные вещи, это [то, что люди называют monad. Понимание монадов интересно, но не требуется, чтобы их использовать.

Answer 2

Реализуйте метод find на Node и создать метод заглушки find для Tree, который мог бы выглядеть следующим образом:

impl<T: Ord> Tree<T> { 
    pub fn find(&self, key: &T) -> bool { 
     match self.root.as_ref() { 
      None => false, 
      Some(x) => x.find(key) 
     } 
    } 
}