层次序列和中序序列求树,根据先序序列和中序序列创建二叉树

已知前序序列和中序序列求后序序列 2023-12-05 10:25 825 墨鱼

已知前序序列和中序序列求后序序列

层次序列和中序序列求树,根据先序序列和中序序列创建二叉树

如果二叉树为空，则结束并返回，否则：(1)访问根节点。 2）前序遍历左子树。 3）预序遍历右子树。需要说明的是，遍历左右子树时仍然采用前序遍历的方法。例：先序遍历结果：ABDECF注：现有一棵二叉树，有n个节点（节点号从0ton-1）。其层序和中序序列已知，找到先序序列。输入描述的第一行是一个整数（1≤n≤50），代表二叉树的节点数；第二行是整数，代表二叉树的层数。

通过中序序列找到根节点索引（根节点是前左子树和后右子树），然后从层次序列中找到对应的左右子树（注意层次序列的顺序，代码中的双循环体现在原来构建的二叉树是基于前序遍历和中序遍历的。注：可以假设例如：前序遍历preorder=[3,9,20,15,7]中序遍历inorder=[9,3,15,20,7 ]返回以下二叉树：

//层次顺序和中序顺序唯一确定一棵二叉树#include#include#includetypedefstructBTNode{chardata;structBTNode*lchild;structBTNode*rchild;}最后两行BTNode行分别输入层次遍历顺序和中序遍历顺序。使用build()函数构建二叉树。首先查找根节点，然后划分左右子树，分别构建两棵子树。并将左右节点分别保存到chandrchararrays中。

ˇ▂ˇ 文章已浏览2.9k次，点赞15次，收藏34次。前言在复习数据结构的时候，遇到这样的问题，遇到了麻烦，所以花了一定的时间复习和总结。以下是我的解题过程。如有错误，请指正_中序层。该过程与建立二叉搜索树（BST）的过程非常相似。将laSq[laIndex]插入到根根的子树中.如果当前根节点为空，则为新节点的位置。如果不为空，则根据两个值的中序顺序，

后台-插件-广告管理-内容页尾部广告（手机）

标签：根据先序序列和中序序列创建二叉树