输入两个串:
string midOrder = "HDIBJEKALFMCNGO";
string firstOrder = "ABDHIEJKCFLMGNO";
输出一棵二叉树。
算法思想很简单,在先序中的第一个节点一定是根节点,此节点在中序中的位置可以将中序分为左右两棵子树。如:
根为A,中序分为:HDIBJEK A LFMCNGO,这两棵子树在使用同样的方法就生成一棵树。
//
核心算法
Node
*
SetTree(
string
&
midOrder,
string
&
firstOrder)
...
{
if
(midOrder.length()
==
1
)
...
{
return
new
Node(midOrder);
}
string
node
=
firstOrder.substr(
0
,
1
);
Node
*
n
=
new
Node(node);
size_ti
=
midOrder.find(node);
size_tj
=
firstOrder.find(midOrder.substr(i
-
1
,
1
));
n
->
left
=
SetTree(midOrder.substr(
0
,i),firstOrder.substr(
1
,i));
n
->
right
=
SetTree(midOrder.substr(i
+
1
,midOrder.length()
-
i
-
1
),firstOrder.substr(j
+
1
,firstOrder.length()
-
j
-
1
));
return
n;
}
中序遍历和后序遍历生成树的算法类似实现。
这里因为每次递归会生成多份string,也创建了大量的额外空间,所以改进此算法,只提供下标即可:
如果思考不清晰,这部分调试起来还是比较困难。需要打印每次递归的信息,最后先使用小数据量,然后打印出来,而不要用gdb调试。源程序是这样打印的:
另外贴上其中的find函数,这里的count其实是找对于start来说的相对位置(师兄说下面这段代码写的很烂,但是烂的凑在一起,竟然没有错,这让我想到了独孤九剑):
这是为什么呢?因为里面使用到多个判断标准..所以改为:
分享到:
相关推荐
本话题主要探讨了如何生成树以及如何通过先序和中序遍历来理解和操作树。首先,让我们详细了解一下这些概念。 二叉树是每个节点最多有两个子节点的树结构,通常分为左子节点和右子节点。在二叉树中,我们可以执行...
[问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
例如,先序遍历常用于复制二叉树,而中序遍历常用于生成排序序列。了解和掌握这两种遍历方式对于理解和设计算法至关重要。 为了更好地理解这些概念,可以动手实现这些操作并用示例数据进行测试。在给定的“树”文件...
在IT领域,数据结构是计算机科学的基础,而树作为一种重要的数据结构,被广泛应用于各种算法设计和问题解决中。本文将深入探讨“数据结构 树的操作 遍历”这一主题,包括二叉树的遍历方法、相关计算以及哈夫曼编码与...
2、分别调用先序、中序、后序遍历算法对前面建立好的二叉链表树进行遍历。要求分别显示遍历后的结点序列。(递归和非递归) 3、调用计算二叉树的结点总数、深度、叶子节点个数算法,统计上述二叉链表树的结点总数、...
比如,在编译器中,前序遍历常用于生成语法树;在数据库系统中,中序遍历可以用于实现B树的查找操作;而在某些数据结构如AVL树或红黑树中,后序遍历对于保持树的平衡至关重要。 了解和掌握二叉树遍历算法,不仅可以...
森林的遍历算法有两种:先序遍历和中序遍历。先序遍历森林是指访问树中第一棵树的根结点,然后先序遍历第一棵树的所有子树构成的森林,最后先序遍历除去第一棵树外剩下的树构成的森林。中序遍历森林是指中序遍历第一...
三、最小生成树算法 本部分涵盖了最小生成树的算法和时间复杂度。 * 题目要求讨论最小生成树的算法和时间复杂度。 四、深度优先搜索和广度优先搜索 本部分涵盖了深度优先搜索和广度优先搜索的算法和应用。 * ...
先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下: /* *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中 * * * */ /*用来生成一个节点*/ function Node(data, left, right)...
综上所述,学习先序输出度为1的结点不仅有助于我们更深入地理解树的结构和性质,还能够在算法设计与实现过程中发挥重要作用。无论是理论学习还是实际应用,掌握这一概念都能够为我们带来实质性的帮助。因此,在学习...
14. **最小生成树算法之Prim算法**:用于找到加权图中的最小生成树。 15. **最小生成树之Kruskal算法**:另一种用于寻找最小生成树的方法。 16. **单源最短路径**:Dijkstra 算法等用于找到从一个节点到其他所有节点...
07-003最小生成树算法:普里姆算法、克鲁斯卡尔算法 07-004双连通图和关节点、源点到其他各点的最短路径 07-005每一对顶点间的最短路径、拓扑排序、关键路径 07-006广义表的定义、表示 07-007创建广义表的存储结构、...
- **图**:图的定义、术语、存储结构,深度优先搜索、广度优先搜索,最小生成树、拓扑排序、关键路径和最短路径算法。 2. **算法设计与分析**: - **排序算法**:简单排序(插入、希尔、冒泡、快速、选择、堆、...
左上是无向网的逻辑结构,图中顶点的初始状态为黄色,算法执行过程中,红色覆盖的顶点和边则表示已加入生成树的顶点和生成树上的边;窗口的下方则显示 closedge 数组中的值。 28. 克鲁斯卡尔算法 图示窗口的左侧为...
遍历分为先序遍历、中序遍历和后序遍历三种方式,它们的非递归算法都有各自的特点。由于递归算法存在效率低和可能被限制的问题,非递归算法在实际中的应用也非常重要。 先序遍历的非递归算法利用了栈的后进先出...
本文件主要涵盖了关于树和图的一些习题,涉及到了树的性质、二叉树的遍历、图的表示以及最小生成树的构造算法。 首先,我们来看树的相关知识。在树的性质中,有一个重要的公式用于计算树中终端结点(度为1的结点)...
2. **树形数据结构**:重点介绍了二叉树(包括二叉搜索树、平衡二叉树、AVL树、红黑树)、堆(最大堆、最小堆)、以及树的遍历算法(先序遍历、中序遍历、后序遍历)等。书中不仅提供了树的各种形态的图示,还详细...