标签: binary-tree

给定一个带有整数,左右指针的二叉树,如何在O(n)时间和O(1)额外内存(没有堆栈/队列/递归)中遍历树？

这个人给出了一个解决方案,该解决方案不是将当前路径编码为整数的O(n)总时间(因此适用于有限深度的树).

我正在寻找经典的解决方案

(SPOILER)

编码子节点中每个节点的父节点.

有两个二叉树T1和T2存储字符数据,允许重复.
如何判断T2是否是T1的子树？.
T1有数百万个节点,T2有数百个节点.

随着算法的进展,我有一棵大树.每个节点都包含set,我认为它是作为平衡二叉搜索树实现的.在创建该节点的子节点之前,每个节点的集合在该节点创建之后应保持固定.

但我担心复制每一套都非常昂贵.相反,我希望每个新创建的节点集合利用父节点集合的所有适当部分.简而言之,我很高兴复制集合的O(log n)而不是O(n).

STL的关联数据结构是否有任何变体可以提供这种部分复制优化？也许在Boost？当然,在Haskell或OCaML中实现这样的数据结构是微不足道的,但是在C++中需要更多的努力.

通常,基于二叉树的抽象可以使用实际的链接节点对象来实现,其中每个节点具有指向它的两个子节点的指针,或者数组,其中索引k中的节点的子节点是2k和2k + 1.

除了节点的小额外内存开销之外,一般的复杂性似乎是相同的.

一个是否有任何具体优势？有趣的是,我已经看到二进制堆倾向于使用数组实现,而二进制搜索树倾向于使用链接节点实现.有什么理由吗？

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

我需要找到一棵树的祖父,在这个例子中,我只有一个祖父,12号(我需要他只有两三个孙子).

这是我到目前为止所尝试的:

int T(struct node * tree){
    int t = 0;
    if (tree == NULL)
        return 0;
    if (tree->left && tree->right)
    {    //In this case i check if we NOT have all the four grandchildrens.
        if (!((tree->left->left) && (tree->left->right) && (tree->right->left) && (tree->right->right)))
        {
            t =  1 + T(tree->left) + T(tree->right); …

专家F#3.0一书的第9章介绍了如何在遍历二叉树时使用延续传递样式来避免堆栈溢出.我编写的树遍历代码几乎与本书中的代码完全相同,但我仍然得到了堆栈溢出.我的代码如下:

type 'a Tree =
  | Leaf   of 'a
  | Branch of 'a Tree * 'a Tree

let rec mkLeftLeaningTree n tree =
  if n = 0 then
    tree
  else
    Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right")

let leftLeaningTree1 = Leaf "left"
let leftLeaningTree2 = mkLeftLeaningTree 30000 leftLeaningTree1
let leftLeaningTree3 = mkLeftLeaningTree 30000 leftLeaningTree2
let leftLeaningTree4 = mkLeftLeaningTree 30000 leftLeaningTree3
let leftLeaningTree5 = mkLeftLeaningTree 30000 leftLeaningTree4
let leftLeaningTree6 = mkLeftLeaningTree 30000 leftLeaningTree5

let sizeContAcc tree =
  let rec …

这是我对两者的理解

B 树索引 :-一般用于数据库列。它将列内容保留为 key 并将 row_id 保留为 value 。它以排序方式保持键以快速找到键和行位置

倒排索引：-一般用于全文搜索。此处，文档中的单词也用作键，以排序方式与文档位置/ID 一起存储为值。

那么 b/w B tree index 和 Inverted index 有什么区别。对我来说它们看起来一样

给定一棵二叉树： 高度为 3 的二叉树

我想找到同一级别的两个节点之间的水平距离，同时计算中间不存在的节点，而不计算节点本身，例如

          f
      /         \
     g           h      
    /  \        /  \        
  a                d    

节点a和d之间的水平距离为 2。

编辑：

请参阅 a 到 d 之间的距离是在同一级别计算的，不包括 a 或 d 的父节点或子节点，而仅包括同一级别的缺失节点。所以 a 到 d 之间的距离将是 a>(x>y)>d 其中 x 和 y 分别是节点 g 和 h 的缺失子节点。因此，不计算目标节点 a 和 d 的水平距离为 2

对于二叉树，广度优先搜索遍历（BFS）是否与预序遍历相同？我对这两种不同类型的遍历有点困惑。任何人都可以向我解释一下吗？此外，预序遍历与深度优先搜索遍历(DFS) 相比如何？

非常感谢！

您好，我制作了一个简单的二叉树并添加了前序遍历方法。在提出一些想法之后，我陷入了寻找一种从traverse_pre()数组中的方法返回每个值的方法上。

class BST:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        if self.left:
            self.left.traverse_pre()
        print(self.value)

        if self.right:
            self.right.traverse_pre()


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

Tree.traverse_pre()

我将如何修改该traverse_pre()函数以返回由节点值组成的数组。有没有这个过程的一个很好的例子让我进一步理解这一点，我有点困惑如何在递归中将值附加到数组中。