实验六、数据结构之二叉树三切点法找遍历序列

秒速五厘米 2023-06-09 15:25 3阅读 0赞

如给一个二叉树如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70][]

求先序，中序，后序遍历序列？

三切点方法如下：

1. 画出如下图案：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 1][]

2. 先序遍历：则标箭头往左如下：（速记左）

先序，则最上面为起点，中序和后续都是最左边为起点。

沿着外围走，则：ABDCEFGH,具体操作如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 2][]

3. 中序遍历：则箭头往下标：（速记中央）

起点最左，沿着外围走，则：DBAECGFH

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 3][]

4. 后续遍历：

起点最左，沿着外围走，则：DBEGHFCA

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 4][]

5. 算法实现见下一个博文

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70]: /images/20230531/e543cd69230d45d595c36f736348f5eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 1]: /images/20230531/8c6ecdea9c4a41259ebf31d44dfc4bd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 2]: /images/20230531/ccf8058f17a245dcb48998413f853d21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 3]: /images/20230531/9e63bc24f2514e78b2cf306ad3bd88bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70 4]: /images/20230531/16f0149a438045b2b655e3b4466a05ff.png