二叉查找树 每个节点存放一个一个整数 中序遍历得到序列为 3 4 5 有多少种画法

2020-10-28 社会 91阅读
1、先观察中序遍历第一个元素A,它应该是整棵树中最左的节点;
2、再观察后序遍历最后一个元素(也是A),他是整棵树中最中间的节点;
3、结合上述两点,可以确定A是树的根节点,而且,这棵树没有左子树;
4、接下来观察后序遍历中的B,他在后序遍历中是A之前的元素,而且结合这棵树没有左子树这一 点,可以确定,B是A的直接右孩子;
5、确定了A、B的位置后,可以观察中序遍历树,A和B之间有EHCF,这就证明了EHCF都是B的左子孙,只要确定EHCF之间的位置关系就可以把它链接上B了;(第6步会说明)
6、为了确定EHCF的相对位置关系,我们先观察中序遍历中,他们的顺序是EHCF,而后序遍历中他们是HEFC,经过几次尝试后,很容易就会发现正确的相对位置了;
7、剩下的IGD也可以按理推断出来
声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com