标签: binary-tree

这是我的作业,我已经考虑了很多,但我无法得到答案,我需要你的指导,请帮助我谢谢

问:

我们在BST中有1到1000的密钥,我们想找到密钥= 363

以下哪些搜索不正确？

    <925, 202, 911, 240, 912, 245, 363>
    <924, 220, 911, 244, 898, 258, 362, 363>

Run Code Online (Sandbox Code Playgroud)

我是Java的初学者,正在寻求帮助.

所以我用Java制作了这个二叉树,我应该实现一个方法,按顺序对所有元素进行排序并将它们转换为字符串.它应该看起来像前."[1,2,3,4]".我使用StringBuilder来做到这一点.

我的方法代码看起来像这样:

/**
 * Converts all nodes in current tree to a string. The string consists of
 * all elements, in order.
 * Complexity: ?
 * 
 * @return string
 */
public String toString() {
    StringBuilder string = new StringBuilder("[");
    helpToString(root, string);
    string.append("]");
    return string.toString();
}

/**
 * Recursive help method for toString. 
 * 
 * @param node
 * @param string
 */
private void helpToString(Node<T> node, StringBuilder string) {
    if (node == null)
        return; // Tree is empty, so leave.

    if …

I have a ordered binary tree:
              4
              |
          |-------|
          2       5
          |
      |-------|
      1       3

叶子指向null.我必须创建一个看起来像双重链接的列表

1<->2<->3<->4<->5

(显然5应该指向1)

节点类如下:

class Node {
    Node left;
    Node right;
    int value;

    public Node(int value)
    {
        this.value = value;
        left = null;
        right = null;
    }
}

如您所见,双重链接列表也是有序(排序)的.

问题:我必须在树中创建链表而不使用任何额外的指针.该left树的指针应该是previous列表的指针和right树的指针应该是next列表的指针.

我想的是:由于树是有序树,因此遍历遍历会给我一个排序列表.但在进行inorder遍历时,我无法看到,在何处以及如何移动指针以形成双向链表.

PS我检查了这个问题的一些变化,但没有一个给我任何线索.

我有一些课.

class TreeNode
{
    public TreeNode Left;
    public TreeNode Right;
    public int Value;

    public TreeNode(int i)
    {
        Value = i;
    }

    public TreeNode AddLeft(int value)
    {
        Left = new TreeNode(value); ;
        return Left;
    }
    public TreeNode AddRight(int value)
    {
        Right = new TreeNode(value);
        return Right;
    }
    public static int GetSum(TreeNode root)
    {
        if(root.Left == null || root.Right == null) return root.Value;
        return root.Value + GetSum(root.Left) + GetSum(root.Right);
    }
}
class Program
{
    static void Main(string[] args)
    {
        var root = …

if (current.leftChild.iData != '+' && current.rightChild.iData != '+')  

对于这行代码,我试图检查当前节点的leftChild和当前节点的rightChild是否=='+'或字符加号.如果其中任何一个不=字符+我想执行其他代码.我得到这一行的空指针异常和我用来调用这行代码的方法.iData只是节点内的信息.

给定以下用于将元素插入BST的算法:

 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

该算法在O(n)最坏的情况下运行.

是否可以使用复杂度较低的算法将元素插入BST O(n),在最坏的情况下？

备注1:这不是作业(为即将到来的考试做准备)

备注2:不使用AVL树木

谢谢

我有一个二叉树,很奇怪:根是最高的数字,另一个是减少...(例如:霍夫曼树)我需要制作一个搜索其中的密钥的算法.

我尝试了很多,但我不知道怎么做=(

有什么建议吗？

比如这样

出于某种原因,我似乎无法让"查找"方法起作用.我认为这与范围问题有关... root.val似乎并没有全局更新.我收到一条错误消息,说AtributeError:'int'对象没有属性'val'这是我的代码:

class BinaryNode:
    def __init__(self, v):
        self.val = v
        self.leftChild = None
        self.rightChild = None
    def get(self):
        return self.val
    def set(self, v):
        self.val = v
    def getChildren(self):
        children = []
        if self.leftChild != None:
            children.append(self.leftChild)
        if self.rightChild != None:
            children.append(self.rightChild)
        return children

class Tree:
    def __init__(self):
        self.root = None
    def setRoot(self, node):
        self.root = node
    def size(self):
        if self.root == None:
            return 0
    def subtreeSize(node):
        return 1 + sum(subtreeSize(c) for c in node.getChildren())
        return subtreeSize(self.root)

class BinarySearchTree(Tree):
    def insert(self, …

我知道这是一个常见的问题,我在Stack Overflow中看到了一些线程,但仍然无法得到它.

这是Stack溢出的公认答案:

"磁盘搜索是昂贵的.B-Tree结构专门设计用于尽可能避免磁盘搜索.因此,B-Tree将更多的键/指针打包到单个节点而不是二叉树.这个属性使得树非常平坦.通常大多数B-Tree只有3或4级深度,并且根节点可以很容易地被缓存.这只需要2-3次寻找在树中找到任何东西.叶子也是这样"填充",所以迭代一棵树(例如完整扫描或范围扫描)是非常有效的,因为您每个块(搜索)读取数百/数千个数据行.

在具有相同容量的二叉树中,您将拥有几十个级别,并且顺序访问每个值将需要至少一次搜索."

据我所知,B-Tree有比BST更多的节点(Order).所以它绝对比BST更平坦,更浅.

但是这些节点又被存储为链表吗？

我不明白他们什么时候说键被读作块,从而最小化I/O的数量.

是不是同样的论点也对BST有利？除了链接将向下？

请有人向我解释一下？

我在Haskell中使用二叉搜索树.

这是我写的代码

data BinaryTree a = Leaf | Node (BinaryTree a) a (BinaryTree a)
 deriving (Show, Eq)
  insert :: (Ord a, Eq a) => a -> BinaryTree a -> BinaryTree a
  insert e (Leaf)= (Node Leaf e Leaf)
  insert e (Node n1 a n2) 
      | e<a=(Node (insert e n1) a n2)
      | otherwise = (Node n1 a (insert e n2))

所以基本上这段代码在BST中插入元素,如果第二个参数被锁定在括号内(例如insert 5 (Node Leaf 2 Leaf)),它可以正常工作,但为了获得我想要的东西,我需要我的程序在两种情况下工作,当括号内的第二个参数,当它不是时(例如insert 5 Node Leaf 2 Leaf)你能否就如何重写这段代码提出建议,以获得上述内容