java - 红黑树需要两次遍历吗

Question

正如我们所知，要获得一棵精确的二叉树，我们需要至少两次遍历（按序和前序/按序和后序）来取回原始树。但是，如果树是红黑树，是否必须进行两次遍历（有序和前序/有序和后序）才能得到原始树？谢谢。

Answer 1

通过提供一个反例，很容易证明按顺序遍历是不够的：

     5B
  3R     10B
1B  4B

      3B
    1B   5R
        4B  10B

这些都是有效的红黑树，其遍历顺序为 (1,3,4,5,10)。因此，仅通过有序遍历其节点是不可能重建红黑树的。

Answer 2

作为参考，“前序或后序与有序配对足以唯一地描述树，而前序与后序在树结构中留下了一些歧义。” 特别是，这个答案通过反例表明仅按顺序遍历是不够的，而这个问答表明前序和后序一起是不够的。因为“红黑树是一种特殊类型的二叉树”，答案是肯定的：至少需要两次遍历，其中一次是有序的。

Answer 3

不，前置或后置遍历就足够了。

由于红黑树是二叉搜索树，因此搜索树属性意味着中序遍历只是所有元素的排序列表，因此是多余的。