进行二叉树还原

前言

要知道怎么进行二叉树还原,首先要知道二叉树先序排列,中序排列,后序排列的概念
下面的地址是关于先序排列,中序排列,后序排列的一些概念
在进行还原之前应该先搞懂这些
地址:https://blog.csdn.net/qq_33243189/article/details/80222629
接下来我们开始做一道关于二叉树还原的题
已知,我们知道一个二叉树的先序和中序排列
先序:ABDFGHIEC
中序:FDHGIBEAC

通过先序排列的A开头可知,二叉树的根节点是A,那么根节点左边的所有字母为FDHGIBE,又根据中序排列F开头可知左边根节点到F截止,如下图所示

图片.png

通过图片可知.FD和B之间夹杂了HGI等字母,所以判断HGI在D的右节点
图片.png

那么HGI在D的右节点该怎么排列呢,通过先序排列ABDF之后的GHI可知,G是GHI的根节点,那么.H就在G的根节点左边,I在G的根节点右边
如下图所示
图片.png

这里看着中序排列数字就可知,ADHGIB和根节点A之前还应该有一个E的节点
图片.png

到这里基本就完事了,因为只剩了一个c节点在根节点的右边
图片.png

到这里就完成了二叉树的整体还原

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容