标签: binary-tree

我有一个具有以下规范的 Java 二叉树，我需要克隆它。

public class Item {

    private final String value;
    public final Item left;
    public final Item right;

    ...

}

看似非常简单的任务让我感到困惑，因为克隆的树必须与原始树对象共享相同的单元格，而不是被复制。

但是，如果要将某个项目添加到原始树或克隆树，则它不得传播到另一棵树。IE。如果要将新项目添加到原始树中，则它不得出现在克隆树中，反之亦然。

此外，这需要在没有递归和任何循环构造的情况下完成。

所以我想知道是否有人能想到这样做，因为我不知道从哪里开始？

以中序方式找到二叉树中的节点，并返回\nPS\xef\xbc\x9a 二叉树可能包含两个具有相同值的节点。\nit 以前序方式很容易做到

Node find(Node root, int val){...}\n

任何人都可以分享解决方案吗？

参考来自 Intro to Algorithms, pg 157。图像有 10 个节点，树的高度为 3。

我的问题是当 h=1 时这如何成立？

天花板(n/2^(h+1))=天花板(10/2^(1+1))=天花板(10/4)=天花板(2.5)=3个节点。但是 h=1 有 4 个节点。

我想在 Haskell 中使用 infinitree :: Tree 定义一个无限树，但想为每个节点设置一个模式，定义每个节点应该是什么。该模式比其父模式多 1。我正在为如何建立一棵树而苦苦挣扎，以及如何以及在何处定义每个节点的模式？

谢谢

假设我有一个平衡二叉树。我希望在树中搜索密钥 k。但是，如果二叉树中不存在 k，它应该给我最接近 k 的下一个最大数字。

例如，假设我将这些数字 [1,5,6,8,10] 作为树中的键。如果我搜索“7”，它应该返回 8，如果我搜索 2，它应该返回 5，等等。

为了能够执行这样的搜索，二叉树必须进行哪些修改？我也想要一个 O(log n) 的解决方案。

任何人都可以帮助我使用 python 中的 bfs 代码吗？它只是打印自我价值，而不是整棵树。

from queue import *

class BinaryTree:
   def __init__(self,info,left,right):
    self.info  = info
    self.left  = left
    self.right = right

def bfs(self): 
    queue = Queue()
    queue.put(self)

    while not queue.empty():
        self = queue.get()
        print(self.info)

        if self.left:
            queue.put(self.left)

        if self.right:
            queue.put(self.right)
        return

nine = BinaryTree("9",None,None)
eleven = BinaryTree("11",None,None)
two = BinaryTree("2",eleven,nine)
one   = BinaryTree("1",None,None)
seven = BinaryTree("7",one,None)
five = BinaryTree("5",seven,two)
three = BinaryTree("3",None,None)
six = BinaryTree("6",None,None) 
four = BinaryTree("4",None,six)
eight = BinaryTree("8",four,three)
ten = BinaryTree("10",eight,five)

ten.bfs()

我的答案只是“10”，而不是整棵树。我找不到错误。

我正在尝试编写一个 JavaScript 函数，该函数比较由 sa 和 b 定义的两个二叉树TreeNode，如果它们在结构和值上相等则返回 true，否则返回 false。

例如比较两个二叉树的值和结构的示例

给定以下课程：

class TreeNode {
  constructor(data, left=null, right=null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

这是我到目前为止尝试编写的代码，将 TreeNode a 和 b 进行映射。

const binaryTreeCompare = (a, b) => {
  if(a==null && b==null){
    return true;
  }else if(a!=null && b!=null){
    return(
      a.data == b.data && binaryTreeCompare(a.left, b.left) && binaryTreeCompare(a.right, b.right)
    );
  }
    else return false;
}

我期望输出为 true 或 false，但这就是我得到的：

ReferenceError: compare is not defined
    at …

所以我在研究树遍历算法。例如，在 Kd 树遍历中，我们的目标是将节点向下遍历到叶子节点。这与其说是树搜索，不如说是从根到叶的遍历。

在这种情况下，递归解决方案就足够了。但是，在像 C 这样的语言中，递归调用函数需要将值压入堆栈并在堆栈帧之间跳转等。标准递归方法类似于：

void traverse(Node* ptr){
    if(ptr.left == null && ptr.right == null) return;
    if(ptr.val >= threshold) traverse(ptr.right);
    else if(ptr.val < threshold) traverse(ptr.left);
}
traverse(root);

因此，考虑到二叉树有一个明确的上限（我相信这也可以扩展到其他树类型），以迭代方式执行此遍历是否会更有效：

Node* ptr = root;
for(int i = 0; i < tree.maxHeight; i++) {
    if (ptr.left == null && ptr.right == null) break;
    if (ptr.val >= threshold) ptr = ptr.right;
    else if (ptr.val < threshold) ptr = ptr.left
}

二叉树的最大高度将是它的节点数，而平衡的将是 log(n)。因此，我想知道迭代解决方案是否有任何缺点，或者它是否确实比简单的递归更快。我在这方面缺少任何概念吗？

我有一个来自此链接的 excel 文件中的表格：

如果Input值是1s，我怎么能把它读成一个 n 元树并总结 Python 中的所有节点？如果它nodes和leaves名称也显示在树上会更好。

         15
     /        \
    8          7
  /  \      /     \
  6   2    2       5
/ | \ |   /  \   / | \
3 3 0 2   2  0  0  2  3 

非常感谢您在 adavance 的帮助。

我的试用代码：

class Node:
    def __init__(self, name, weight, children):
        self.children = children
        self.weight = weight
        self.weight_plus_children = weight

    def get_all_weight(self):
        if self.children is None:
            return self.weight_plus_children
        else:
            for child …

仅使用基本 R 功能/工具创建二叉树的最佳方式是什么（假设在这种情况下，最佳意味着“创建或访问的最快方式”）？我假设某种形式的递归和/或使用环境操作的数据结构是必要的？

更重要的是，我希望二叉树的创建被参数化为应该生成什么类型​​的树（例如：一个完美的，其中所有节点都有两个孩子？）。

例子：

my_tree <- grow_tree(perfect = FALSE, max_height = 3)
print(my_tree)

my_tree[1]
1

my_tree[1][left]
2

my_tree[1][right]
3

my_tree[1][left][left]
4

应该是一棵树的表示，看起来像：

    1
   / \
  2   3
 /
4

注意：随意使用 S3 或 S4，考虑到它们是在基础 R 中提供的。但是，如果没有它们，看到解决方案会很有趣。