问题标签 [preorder]

我有一种打印树内容的方法：

我的树的内容读取正确，但我想格式化树，使其看起来更好。现在，对于一棵树：

打印内容：

但我想添加一些缩进，使其内容为：

格式为：

我只是对递归有点迷失了。谢谢！

一个令人痛苦的愚蠢问题，我几乎羞于问。我一直在搜索过去 4 个小时，测试了不同的算法，在纸上尝试了很多，但仍然无法让它工作。

我将为您省去项目实施的细节，但基本问题是：“您如何处理在预购二叉树中插入节点。

通过 Pre-Order BST，我的意思是所有节点都应该以这样的方式插入，即使用 pre-order 遍历（例如用于打印）遍历树应该按升序打印节点。

我只需要一个简单的算法。我尝试了一个简单的插入算法here（在stackoverflow上，但它似乎不正确（也在纸上尝试过））；。

节点基本上是这样的：

插入数据只是一个唯一整数列表。我创建一个以 int 为键的节点，然后应该将该节点添加到树中。我有根节点，它以 NULL 指针开始。

抱歉，如果有任何不清楚的地方。

谢谢您的帮助！

编辑：根据下面提供的算法，这就是我想出的：

给定一个未排序的节点数组，其中节点定义为：
Node { int id; int parent_id; string label; }

每个节点都有自己唯一的 id。parent_id在树中识别其父项。问题是如何对树进行前序遍历？（不一定是二叉树）

这是一个困扰我好几天的面试题。我能想到的是使用一个哈希映射map<int,list<node> >，其中 key 是 parentid。那我就不能更进一步了。我应该从地图构建树并进行前序遍历，还是有直接从地图中进行的好方法？那怎么办？任何提示表示赞赏！

我想在二叉树上进行前序遍历时将元素添加到链接列表。我不想破坏BT，只是复制一个链表中的元素。这是我的代码片段。

上面的代码什么也没打印。我认为问题在于使用 head = List_insert(head, node->data); 在预购功能中。任何帮助都将不胜感激。

给定完整二叉树的前序遍历，其中每个节点都标记为叶节点或内部节点，是否有一个好的算法来找到树的高度？例如，如果 N 代表一个内部节点，L 代表一个叶子，那么给定前序遍历 NLNNLLL，高度将为 3。

我有一个任务，我需要一些方法方面的帮助。

所以我有一棵这样的树：

我的方法是：

讲师给出了树的简单实现。该类称为 BinaryTree，如果您想创建一个节点链接到它，那么您指定左右子 BinaryTree 节点是什么。

一个节点有两个链接（一个在左边，另一个在右边子节点）并且没有到头的链接。

因此，使用当前方法，我能够成功地进行前序遍历，我通过编写存储在节点上的元素的打印语句来进行测试。

但是当我运行测试时，它告诉我来自 A 的下一个预购节点是 B，来自 K 的下一个预购节点抛出一个空异常，但应该是 I？

关于我哪里出错的任何想法？变量 prev 应该包含对访问的最后一个节点的引用，所以如果它等于节点 v（这是我指定的节点，返回 v 之后的节点），我不应该得到下一个节点吗？

I have following function to print trees in in order that works properly:

This is my preorder printing function:

As i'm too stupid to figure it out how to print it separated the way like the inorder function i hope you guys can help me out!

thanks!

Update:

Preorder function works now, so is this the right postorder function?

如果 T 是具有多个节点的有序树。T 的前序遍历是否可能与 T 的后序遍历以相同的顺序访问节点？如果“是”，请您举个例子。如果“否”，您能否解释为什么它不会发生？

绘制前序、后序和中序的规则是：

1. 前序遍历：根、左、右
2. 后序遍历：左、右、根
3. 中序遍历：左根，右

例如，如果我们有这样的表达式：

ABCDEFGHIJKL,

我怎样才能为这个表达式分别绘制（预购、后购和有序）。有可能我们对每个都有不同形式的树（预购、后购和有序）。（即两种形式的预购）。如果我们同时拥有 (pre-order and and in-order) 或 (post-order and in-order)，我们就可以拥有唯一的树。在预购中，第一个节点是根节点（即“A”是根节点）。在后序中，最后一个节点是根节点（即“L”是根节点）。

绘制这些树是否有任何总体公式或“规则”？我画不出来

编辑：我的意思是如何从以下遍历的每个前序、后序和中序构造树：

ABCDEFGHIJKL,

我使用修改后的预排序树将 GEO 位置存储在我的应用程序中的单个表 LOC_TABLE 中。例如，希腊的子树示例如下所示：

TYPE列用于存储位置类型（3 - 国家，4 - 城市）。如您所见，Crete 存储为 city，其中包含其他城市（例如Vamos和Rethymno）作为​​其子级。

我需要执行两种类型的查询：

1）获取特定父项下特定类型的所有位置。

2）获取特定父级下特定类型的所有顶级位置：仅Crete Isl.在查询希腊境内的城市时应返回提供的位置示例，因为Crete Isl.没有城市类型的父级，而城市Vamos和Rethymno具有城市类型的父级 -Crete Isl.

在每种情况下执行最快的查询是什么？

对于第一种情况，我考虑使用两个查询（首先，获取希腊的 LFT 和 RGT，第二个获取类型 = 4 的所有位置，它们具有适当的 LFT 和 RGT）或使用某种连接来一步获取所有位置. 哪个是最好的方法？

对于第二种情况，我目前没有任何合适的想法。我尝试了简单的子选择：

但是太长了。

我不介意添加更多列并用一些值填充它们，这将有助于加快这两种类型的查询。但我需要快速获取数据。

谢谢。