数据结构笔记——由遍历序列构造二叉树

た 入场券 2023-02-13 08:05 97阅读 0赞

目录

一、不同二叉树的中序遍历序列

二、前序+中序遍历序列

三、后序+中序遍历序列

四、层序+中序遍历序列

五、若前序、后序、层序序列两两组合?

六、总结


一、不同二叉树的中序遍历序列

中序遍历:中序遍历左子树、根结点、中序遍历右子树

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70

前序遍历:根结点、前序遍历左子树、前序遍历右子树

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1

后序遍历:前序遍历左子树、前序遍历右子树、根结点

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2

结论:若只给出一棵二叉树的前、中、后、层序遍历序列中的一种,不能唯一确定一棵二叉树

20200527215552929.png

二、前序+中序遍历序列

20200527215840965.png

前序遍历序列:根结点 左子树的前序遍历序列 右子树的前序遍历序列

中序遍历序列:左子树的中序遍历序列 根结点 右子树的中序遍历序列

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3

例1:

20200527220032422.png

20200527220055298.png

例2:

20200527220308142.png

20200527220324436.png

三、后序+中序遍历序列

后序遍历序列:左子树的中序遍历序列 右子树的中序遍历序列 根结点

中序遍历序列:左子树的中序遍历序列 根结点 右子树的中序遍历序列

20200527220445868.png

例:

20200527220458525.png

20200527220324436.png

四、层序+中序遍历序列

层序遍历序列:根结点 左子树的根右子树的根

中序遍历序列:左子树的中序遍历序列 根结点 右子树的中序遍历序列

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4

例1:

20200527220742792.png

20200527220324436.png

例2:

20200527220928530.png

20200527220946384.png

五、若前序、后序、层序序列两两组合?

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5

六、总结

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6

发表评论

表情:
评论列表 (有 0 条评论,97人围观)

还没有评论,来说两句吧...

相关阅读

    相关 数据结构————

    遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质