标签 数据结构 下的文章

用 Graphviz 绘制一棵漂亮的二叉树

起因

之前用 Rust 写了一个 AVL 树的实现，就很自然的想把树用可视化的图像画出来，在一波搜索过后，最后都指向了一位叫 Emden Gansner（ Graphviz 主要贡献者之一） 的大佬在 2010 年写的一段脚本，原作者是在邮件列表（链接1，链接2）中回复别人的问题时提供的这段脚本，由于这个邮件列表原来的存档网站已经无法访问，现在能搜到的基本上都是别人对这段脚本引用，比如： stackoverflow。

不过这个 gvpr 我实在是看不懂，所以我希望能够直接使用 dot 来绘制二叉树，这样在生成图像的时候就只需要使用 dot 命令行工具而不需要额外的脚本了。

尝试

但是事情看起来并没有那么简单，假如我们现在有一个文件 tree.dot：

digraph G {
    node [shape=circle]
    edge [arrowhead=vee]
    8 -> 4
    4 -> 2
    2 -> 1
    2 -> 3
    4 -> 6
    6 -> 5
    6 -> 7
    8 -> 10
    10 -> 9
    10 -> 12
    12 -> 11
}

- 阅读剩余部分 -

用 Rust 实现一个 AVL 树

什么是 AVL 树以及 AVL 树的一些原理就不介绍了，我们直接讲如何用 Rust 来实现它。

结构体及 trait 定义

参考一般 AVL 树的实现，我定义了一个结构体 TreeNode 以及一个类型别名 AvlTreeNode：

pub type AvlTreeNode<T> = Option<Box<TreeNode<T>>>;

#[derive(Clone, Debug)]
pub struct TreeNode<T: PartialOrd> {
    val: T,
    height: i32,
    left: AvlTreeNode<T>,
    right: AvlTreeNode<T>,
}

使用类型别名可以了少打几个字母以及好看一点。

还定义了一个 trait AvlTree：

pub trait AvlTree<T: PartialOrd> {
    fn new(val: T) -> Self;
    fn height(&self) -> i32;
    fn insert(&mut self, val: T);
    fn delete(&mut self, val: T) -> Self;
}

- 阅读剩余部分 -