标签: binary-tree

问题：我需要能够通过索引从未知高度的完美二叉树中递归地检索节点。

由于高度属性未知，似乎唯一有意义的索引形式是广度优先索引（根据标题）：

          0
    1           2
3       4   5       6

问题是，在每个节点似乎很难知道要采取哪个方向，以及如何将递归请求中的索引转换为该子节点......或者也许我只是没有思考清楚。

Node Navigate(Index):
Index 0: return this;
Index 1: return Left.Navigate(0);
Index 2: return Right.Navigate(0);
Index 3: return Left.Navigate(1);
Index 4: return Left.Navigate(2);
Index 5: return Right.Navigate(1);
Index 6: return Right.Navigate(2);
...
Index 7: return Left.Navigate(3);
Index 8: return Left.Navigate(4);
Index 9: return Left.Navigate(5);
Index 10: return Left.Navigate(6);
Index 11: return Right.Navigate(3);
Index 12: return Right.Navigate(4);
Index 13: return Right.Navigate(5);
Index 14: return Right.Navigate(6);

模式很清晰 - 但如何以编程方式 - …

设 n 为二叉树的节点数，那么找出二叉树的最小高度的通用函数项是什么？

我认为n=floor(log2(n))+1。但是，我想，我错了。

如何编写函数来返回奇数高度节点的值之和与偶数高度节点的值之和的差。考虑到二叉树的根节点高度为 1

输入：

                                      1
                              2                3
                          4        5       6        7
                      8     9  10    11  12  13   14  15

输出：-74 解释：

[ (1 + 4 + 5 + 6 + 7 ) - (2 + 3 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = -74 ]

代码：

public static int diff(Node n) {
    if (n == null)
        return 0;
    return Sum(n) - Sum(n.left) - Sum(n.right);

}
public static int Sum(Node root) { …

我编写了一个递归函数来查找二叉树的最小值（假设它是无序的）。

代码如下。

//assume node values are positive int.
int minValue (Node n) {
if(n == null) return 0;
leftmin = minValue(n.left);
rightmin = minValue(n.right);
return min(n.data, leftmin, rightmin);
}

int min (int a, int b, int c) {
int min = 0;
if(b != 0 && c != 0) {
if(a<=b) min =a;
else min =b;
if(min<=c) return min;
else return c;
}
if(b==0) {
if(a<=c) return a;
else return c;
}
if(c==0) {
if(a<=b) return a;
else return b; …

我编写了几个函数来计算二叉树的大小。第一个（函数 1）工作得很好，并且是在类外部声明的，它不是类的成员函数。然而，第二个是类的成员函数给了我奇怪的结果。我很困惑！任何帮助，将不胜感激。

Function 1
    def size(root):
        if root is None:
            return 0
        else:
            return size(root.left)+ 1+ size(root.right)


Function 2
    def size(self):
        if self.left is None or self.right is None:
              return 0
        else:
              return self.left.size()+1+self.right.size()

我有以下二叉树

    3
   /  \
  5     2
 / \    /
1   4   6

我的周末是递归的，所以请耐心等待，我需要你的帮助来追踪它以使其正确。

我有以下代码，它的作用是在 Post Order 中打印节点。所以答案是 1 4 5 6 2 3

void Postorder(Node root) {

if(root == null){
    return;
}

Postorder(root.left);
Postorder(root.right);
System.out.print(root.data + " ");
}

让我们追踪：

Root = 3 (top node), not null, Root.left(5) - 回到函数

Root = 5, Not null, Root.left(1) - 回到函数

Root = 1, Not null, Root.left(null), continue, Root.right(null)

打印 1

现在这是我感到困惑的地方，此时Root = 1，我不知道如何回到 5 然后转到逻辑中的正确节点。另外，当我回到 5 时，我在哪里检查 1 是否被访问过？

我很迷惑。 …

因此，正如标题所暗示的那样，任何人都拥有/知道一种算法（如果可能的话，用java）来生成给定叶子数量的所有可能的二叉树，如下面第二个链接的示例所示？

` N                  N                  N\n / \\                / \\                 /\\\nN   N               N  N               N  N\n/\\   /\\             /\\                     /\\\nN  N  N N           N  N                    N N\n                   / \\                        /\\\n                   N  N                       N N \n

我\xc2\xb4已经去过这个，这个，这个和这个，但我已经尝试实现每个，他们不\xc2\xb4t做我\xc2\xb4m寻找或没有正确解释的事情。如果我必须首先生成所有可能的字符串，然后将它们解析为树类型（父子关系），第一个将需要大量计算，而第二个不打印所有树。因为，例如，如果我像上面的示例一样通过指定 3 个内部节点来执行，它只会打印一棵树（左边的那棵）。我通过研究加泰罗尼亚数字知道，即使对于少量节点，树的数量也会增长很多，但对于少量节点来说是一个有用的工具。

我正在练习递归并尝试从链表实现 BST。我尝试将解决方案从这里转换为 R: Create Balanced Binary Search Tree from Sorted linked list

给定一个向量，vec我想找到 BST，例如：

  0
  / \
 -3   9
 /   /
-10  5


vec <- c(-10,-3,0,5,9)

这是我尝试递归解决这个问题，但它不起作用：

tobt <- function(vec, start, end) {
  if (start > end) return(NA)
  mid <- start + (end - start) / 2
  left <- tobt(vec, start, mid-1)
  right <- tobt(vec, mid+1, end)
  return(c(left, right))
}

tobt(vec, 1, 5)

我的错误在哪里？

考虑二叉树，其中每个节点要么是叶子节点，要么恰好拥有两个子节点（左右，我们认为是不同的）。n节点上有多少种不同的树？
例如：
- 3 个节点 -> 1 棵树，
- 4-> 0 棵树，
- 5 -> 2 棵树，
- 6 -> 0 棵树，
- 7 -> 5 棵树，
- 等等......
有什么公式对于这个序列？我已经找到了所有可能的二叉树（加泰罗尼亚数）的公式，但我正在寻找完整的树。

我有以下问题：

“树的高度是树的最长分支的长度。从高度的定义来看，一个有n个元素的堆的高度是多少？用你的答案给出一个清晰准确的解释。”

堆=二叉树

我知道完整二叉树的数量是 2^(n° of levels - 1)

到目前为止，我尝试了以下方法：

如果有 3 个堆（2 个完全二叉树和 1 个非完全二叉树），使得：

• 堆 A = 是一个完全二叉树，高度为 H
• 堆 B = 是一个高度二叉树，其节点比 A 多但小于 C（所以与 C 具有相同的高度 - 我认为？）
• 堆 C = 是高度 H + 1 的二叉树

我可以说 B 的高度介于 A 和 C 的高度之间，B 的元素数量介于 2^(n° A - 1 级) 和 2^(n° C - 1 级) 之间。

但我不确定如何确定具有 n 个元素的堆的高度。