• 欢迎访问废江网站,承蒙遇见 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏极客公园吧

二叉树四种遍历,根据前中,后中遍历序列求二叉树

算法总结 站点默认 5个月前 (05-09) 119次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

二叉树代码

代码讲解

存储结构


采用指针+结点来存储二叉树,链表栈也是如此, BTNode本身也是一个指针节点,可以指向和其一样结构的地址,所以,struct结构体中的结点也是struct结构体类型

根据中后序遍历求树思路


先观察后序遍历和中序遍历的数组分析一下,可以发现,后序遍历的最后一个值就是根节点,又可以从中序遍历中找出根节点,中序遍历的根节点前面都是左子树,根节点的后面都是右子树;这里所说的左右子树是相对于根节点A的。那么,现在我们得到的数据有,根节点A,根节点A左边的所有左子树x,根节点A右边的所有右子树y。对于x,y两棵树,就是和总树一样。又可以使用同样的方法去求根节点和左右子树。这就是递归方法了。
如何把求出的根节点存到结点表示的树中?在使用函数求出根节点A后,在使用函数递归调用,求出的A的左边的左子树的根节点,不就是根结点A的左结点吗?

这个问题也解决了,最终函数会返回一个头结点root给我们,并且已经帮我们拼接好了root结点下面的所有结点。

指针与数组知识


运行结果:
0x6ffdd0
1
3
0x6ffdd0
1
2
d-b: 0
————————
abcd
cd


极客公园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:二叉树四种遍历,根据前中,后中遍历序列求二叉树
喜欢 (0)
[17730061672]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址