标签: binary-tree

这是有问题的二叉树.叶子是a,b,c,d,边缘标记为0或1.

    .
   / \
  a   .
     / \
    b   .
       / \
      c   d

在我看来,它是一个完整的二叉树,因为每个节点都是一个叶子或有两个子节点,但我有这种感觉,我们被告知它不是一个完整的二叉树.如果没有,为什么不呢？

如果节点的子节点是叶子,那么这不算作子节点吗？

我必须在haskell中编写一个函数来检查两个二进制树是否是彼此的镜像.这是我到目前为止,但我不知道True && isMirrorImages l1 r2 && areMirrorImages r1 l2是否是正确的方法.我试图用递归调用areMirrorImages函数的结果来逻辑AND True.

-- Tests whether two BinaryTrees are mirror images of one another
areMirrorImages :: (Eq (BinaryTree a), Eq a) => BinaryTree a -> BinaryTree a -> Bool
areMirrorImages Empty Empty = True
areMirrorImages _ Empty = False
areMirrorImages Empty _     = False
areMirrorImages (Node x1 left1 right1) (Node x2 left2 right2) = 
    if (x1 == x2 && left1 == right2 && right1 == left2)
then True && (areMirrorImages left1 right2) && …

我正在尝试决定使用哪种数据结构.

假设我有1000万个键,其中包含指向包含某些数据的唯一对象的指针.

密钥是UUID将它们视为16字节二进制数组.UUID是使用高质量的随机数生成器生成的.

我一直在考虑以下内容,但想知道速度和内存消耗方面的优缺点是什么.一些公平的估计,64位平台上的最佳/最差/平均情况会很好.

我需要能够插入几乎无限的项目.

二叉树哈希表基数树(基于位或2位多路)

我需要的操作是:插入,删除,搜索

我喜欢基数树的想法,但它被证明是最难实现的,我没有找到一个合适的实现,我可以将其纳入商业产品.

我想在我的Parametrized BinaryTree类中添加Bi-Directional Iterator(就像std :: set导出的Iterator),但是我无法想出任何算法.

简单的二叉树节点结构是,它包含三个指针,左,右,父:

我想绘制一个带有图形框架(Qt)的二叉树,如下所示:

        9
       /  \
      1    10
    /  \     \
   0    5     11
  /    /  \
 -1   2    6

但是我为每个节点设置X和Y都有问题,你是否知道设置和固定位置？(我只有每个节点的高度和左 - 儿童和右儿童)

我有问题,我无法弄清楚我必须如何决定我的功能indexJ必须在每一步中选择哪个子树遍历我的平衡二叉树 - JoinList.

想法是缓存每个子树的大小(数据元素的数量).然后可以在每个步骤使用它来确定所需索引是在左侧分支还是右侧分支中.

我有这个代码:

data JoinList m a = Empty
                  | Single m a
                  | Append m (JoinList m a) (JoinList m a)
                  deriving (Eq, Show)

newtype Size = Size Int
  deriving (Eq, Ord, Show, Num)

getSize :: Size -> Int
getSize (Size i) = i

class Sized a where
  size :: a -> Size

instance Sized Size where
  size = id

instance Monoid Size where
  mempty  = Size 0
  mappend = (+)

我写的功能: …

我希望这是一个可以接受的问题.我理解递归的思维模式,我想要考虑基本情况然后是递归情况,但是考虑到一些比较困难的BST问题,我只是画空白而感觉就像我迷失了,没有一个好的方向.

以链接列表为例,似乎有一种模式可以解决问题,但BT似乎要么你知道也要不知道.任何提示/指针？我似乎已经解决的唯一概念是,如果我正在处理空节点并且我想对它们或它们做一些事情,我将把它作为一个案例

if(root == null)
     //do something

或者如果我没有与null节点有任何关系,那么我使用倒置的基本情况

if(root != null)
     //do stuff
else 
     //do nothing for null case

但即便如此,我还是会对下一步感到茫然.我想这是一个我遇到的问题的例子,不知道如何接近.我不一定在寻找答案,只是处理这类问题的潜在策略(以及常规的二叉树问题).

编写一个方法numberNodes来更改存储在二叉树中的数据,为每个节点分配以1开头的顺序整数,以便预先遍序遍历将按顺序生成数字(1,2,3等).例如,给定左下方树引用的树,调用tree.numberNodes();将覆盖现有数据,将节点值从1分配给6,以便生成树的预先遍历1, 2, 3, 4, 5, 6.

你不要改变树的结构.您只是更改存储在数据字段中的值.您的方法应返回树中有多少节点的计数.

假设您要将此方法添加到IntTree类中,如下所示:

 public class IntTree {
     private IntTreeNode overallRoot;
     ...
 }

在盯着代码之后,我想我应该用我int count的方法来确定我是否前往左根或右根,因为它是一个二叉搜索树但是我仍然无法实现这个功能......啊编码块!

我正在研究红黑树,我正在阅读Cormen的"算法导论"一书.现在我尝试使用书中描述的伪代码 - RB-INSERT-FIXUP(T,z)创建数字为1-10的红黑树.这是截图

一切都很好,直到我在树中插入数字"6".根据伪代码我得到以下结果

你可以看到所有的红黑树要求都满足了,但我很困惑,因为我知道每一步都应该平衡红黑树.

我可以用"2"和"4"手动执行"左旋"程序并更改颜色.在这种情况下,我将得到以下结果,这是适当平衡的

所以我的问题是:

有没有不平衡的树可以吗？或者我在插入节点期间遗漏了什么？

我有一个二进制搜索树，其中每个节点代表一个游戏长度。我必须返回一个字典，其中的键是游戏的长度，值是该长度的游戏数。递归调用遍历树中的每个节点，但返回错误的字典。我很肯定问题是我如何退还字典。任何帮助将不胜感激

game_len = {}
if not node.children:
    key = len(node.possible_next_moves())
    if key not in game_len:
        game_len[key] = 1
    else:
        game_len[key] += 1
else:
    key = len(node.possible_next_moves())
    if key not in game_len:
        game_len[key] = 1
    else:
        game_len[key] += 1
    [game_lengths(child) for child in node.children] 
return game_len

这是用于查找二叉树最大深度的伪代码:

 maxDepth(Node N)

1. If Nodes is leaf node then return 0

2. Else

     (a) Get the max depth of left subtree recursively  i.e., 

          call maxDepth( N->left-subtree)

     (a) Get the max depth of right subtree recursively  i.e., 

          call maxDepth( N->right-subtree)

     (c) Get the max of max depths of left and right 

          subtrees and add 1 to it for the current node.

         max_depth = max(max dept of left subtree,  
                             max depth of right subtree) 
                             + 1
     (d) Return max_depth

我对这个算法的最坏情况感到困惑.这个伪代码的复杂性将是O(n).这个算法的最坏情况是什么？为什么？