zero4rs 2.0.0

use self::BinaryTree::*;

/// T类型值的有序集合
#[derive(Clone, Debug, serde::Serialize, serde::Deserialize)]
pub enum BinaryTree<T> {
    Empty,
    NonEmpty(Box<TreeNode<T>>), // 一个指向位于堆内存的 TreeNode 的指针
}

/// 用于表示二叉树的节点
#[derive(Clone, Debug, serde::Serialize, serde::Deserialize)]
pub struct TreeNode<T> {
    pub element: T,
    pub left: BinaryTree<T>,
    pub right: BinaryTree<T>,
}

// BinaryTree 的按序遍历状态
pub struct TreeIter<'a, T: 'a> {
    // 树节点引用的栈, 因为使用的是 Vec 的 push 和 pop 方法, 所以栈顶是向量的末尾
    // 节点迭代器将从栈顶取得下一个值, 未访问的祖先节点在下边, 如果该栈空了，则迭代结束
    pub unvisited: Vec<&'a TreeNode<T>>, // '
}

impl<'a, T: 'a> TreeIter<'a, T> {
    // 常见的操作是先将树左边的节点推到栈里, 为此, 在迭代器上定义这么个一个方法
    pub fn push_left_edge(&mut self, mut tree: &'a BinaryTree<T>) {
        while let NonEmpty(ref node) = *tree {
            self.unvisited.push(node); // 最左边的节点在栈的上边
            tree = &node.left;
        }
    }
}

// 实际遍历树
impl<'a, T> Iterator for TreeIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        // 查找迭代必须产生的节点, 或者结束迭代
        let node = self.unvisited.pop()?;

        // 当前节点后面的下一个节点是当前节点右子节点的最左子节点, 因此把它推进栈里
        self.push_left_edge(&node.right);

        // 产生对节点值的引用
        Some(&node.element)
    }
}

// 接下来在树的共享引用上实现 IntoIterator, 调用 BinaryTree::iter 返回迭代器
impl<'a, T: 'a> IntoIterator for &'a BinaryTree<T> {
    type Item = &'a T; // 这个 IntoIter 定义将 TreeIter 作为 &BinaryTree 的迭代器类型
    type IntoIter = TreeIter<'a, T>; // '

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

// 给 BinaryTree 定义一个 iter 方法, 返回二叉树的迭代器
impl<T> BinaryTree<T> {
    // 根据给定的值，创建新的二叉树节点
    pub fn make_node(value: T, left: BinaryTree<T>, right: BinaryTree<T>) -> BinaryTree<T> {
        NonEmpty(Box::new(TreeNode {
            element: value,
            left,
            right,
        }))
    }

    pub fn iter(&self) -> TreeIter<'_, T> {
        let mut iter = TreeIter {
            unvisited: Vec::new(),
        };

        iter.push_left_edge(self);

        iter
    }
}

impl<T: Ord> BinaryTree<T> {
    pub fn add(&mut self, value: T) {
        match *self {
            Empty => {
                *self = BinaryTree::make_node(value, Empty, Empty);
            }
            NonEmpty(ref mut node) => {
                if value <= node.element {
                    node.left.add(value);
                } else {
                    node.right.add(value);
                }
            }
        }
    }
}