我正在研究一个小算法,它可以按照级别顺序构建二叉树。我得到了一个数组,我必须使用其中的值按级别顺序构建二叉树。示例:arr inarr[5]={1,2,3,4,5};
给定这样的数组,我需要填写一个二叉树,看起来像这样:
1
/ \
2 3
/ \ / \
4 5 * *
(*为NULL)节点是基本的二进制节点,具有左指针和右指针以及用于保存数组中值的int的空格。
我理解根据树的高度遍历树的概念,一次遍历一个层次,但我不确定以这种方式构建树的正确逻辑。
按级别遍历树的“自然”方式是使用队列。因此,直观地说,进行反向运算的算法可以使用队列来记忆下一个要处理的节点。
这种算法将遵循以下原则:
0
下面的伪代码从包含其by遍历级别的数组中构建树
Node * build_from_level_order(int a[], int n)
{
Queue q; // this is a queue of pointers to nodes
Node * root = (Node*) malloc(sizeof(Node));
root->key = a[0]; root->left = root->right = NULL;
q.put(root);
for (int i = 1; i < n; /* advancing of i is inside */)
{
Node * p = q.get();
Node * l = (Node*) malloc(sizeof(Node));
l->key = a[i++]; l->left = l->right = NULL;
p->left = l;
q.put(l);
if (i < n) // last level could end in a left node, this test prevents to see an inexistent right node
{
Node * r = (Node*) malloc(sizeof(Node));
r->key = a[i++]; r->left = r->right = NULL;
p->right = r;
q.put(r);
}
}
return root;
}
问题内容: 首先,这个问题不是这个问题的重复,而是在此基础上建立的。 以该问题中的树为例, 您将如何修改程序以进行打印, 而不是一般 我基本上是在寻找最有效的方法的直觉- 我有一种方法,涉及将结果附加到列表中,然后遍历它。一种更有效的方法可能是在弹出每个级别时存储最后一个元素,然后再打印出新行。 有想法吗? 问题答案: 一次只建立一个级别,例如: 编辑 :如果您希望在最大消耗的“辅助”内存中节省少
假设您有一个按级别顺序填充的二叉树,即每个级别都在该级别节点的任何子级之前填充。这样的树可以通过其水平顺序遍历来唯一定义。例如 {1,2,3,4,5,6} 是 对其进行预序遍历将生成数组{1,2,4,5,3,6} 有没有办法将这些数组中的一个直接转换为另一个数组,这比生成实际树并在其上预先形成实际遍历更快?(对于具有 n 个节点的树)
我正在尝试编写一个函数,该函数将使用级别顺序遍历将一个元素插入到二叉树中。我的代码遇到的问题是,当我在树中插入一个新节点后打印级别顺序遍历时,它以无限循环的方式打印元素。1,2,3,4,5,6,7,8这个数字一直在飞驰过终点站。我将感谢任何关于如何补救这种情况的指示和建议。 这是我通过修改级别顺序遍历技术将一个元素插入到树中的地方 主
问题内容: 我必须在Java中创建一个算术评估器。为此,我必须在二叉树中解析一个代数表达式,然后计算并返回结果。因此,对于第一步,我如何解析二叉树中的表达式?我知道理论,但是我的问题是如何用Java做到这一点。 但是我缺少基本的技巧或方法。我知道如何创建节点(我有一个带有returnNodeValue,isLeaf,isDoubleNode,isSingleNode等方法的类),但我认为我需要一种
我创建了一个名为Element的新o类对象,它有很多值“degree” 我想创建一个包含以下元素的优先级队列: 程序将打印: 但我想: 所以我想做的是,度值越大的元素优先级越高,被优先考虑。第二个问题是:如果两个元素具有相同的度值,那么它们将按哪个顺序取?
我正在尝试对二叉树进行级别顺序遍历。但诀窍是代替正常的级别顺序遍历,我想做另一种选择。对于例如。 普通等级顺序遍历 : 我要找的是我们打印根。现在,对于每一个偶数级,我都想逆时针旋转,对于每奇数级,都会顺时针旋转: 对于这种遍历,输出应该是: 这是我到目前为止尝试的,但这产生的输出与我试图实现的输出略有不同: 该程序产生以下输出: < code>1 3 2 5 4 7 6 10 11 9 8 我需