标签: binary-tree

在实现堆结构时,我们可以将数据存储在一个数组中,使得位置i的节点的子节点位于位置2i和2i + 1.

我的问题是,为什么我们不使用数组来表示二进制搜索树,而是处理指针等？

谢谢

我想知道我们是否可以使用二叉搜索树来模拟堆操作(插入,找到最小值,删除最小值),即使用BST来执行相同的工作？

这样做有什么好处吗？

我最近完成了为我正在开发的项目实现二进制搜索树.它进展顺利,我学到了很多东西.但是,现在我需要实现一个常规的二进制树...由于某种原因我难以理解.

我正在寻找一种方法来做我的InsertNode函数..

通常在BST中,您只需检查数据<root然后插入左侧,反之亦然.但是,在普通的二进制树中,它只是从左到右填充,一次一个级别.

任何人都可以帮我实现一个函数,只是从左到右添加一个新的节点没有特定的顺序？

这是我的BST插入:

void Insert(Node *& root, int data)
{
  if(root == nullptr)
  {
    Node * NN = new Node;
    root = NN;
  }
  else
  {
    if(data < root->data)
    { 
      Insert(root->left, data);
    }
    else
    {
      Insert(root->right, data);
    }
  }
}

我试图找到二叉树的尾递归折叠函数.鉴于以下定义:

// From the book "Functional Programming in Scala", page 45
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

实现非尾递归函数非常简单:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B =
  t match {
    case Leaf(v)      => map(v)
    case Branch(l, r) => 
      red(fold(l)(map)(red), fold(r)(map)(red))
  }

但现在我正在努力寻找尾递归折叠函数,以便@annotation.tailrec可以使用注释.

在我的研究过程中,我发现了一些例子,其中树上的尾递归函数可以例如使用自己的堆栈计算所有叶子的总和,然后基本上是a List[Tree[Int]].但据我所知,在这种情况下它只适用于添加,因为无论您是首先评估运算符的左侧还是右侧都不重要.但对于广义折叠来说,它是非常相关的.为了表明我的意图,这里有一些示例树:

val leafs = Branch(Leaf(1), Leaf(2))
val left = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
val right = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
val …

我知道在二叉搜索树上的有序遍历(VISIT LEFT,VISIT ROOT,VISIT RIGHT)给出了一个排序结果.但我需要在二叉树上进行后序遍历(VISIT LEFT,VISIT RIGHT,VISIT ROOT),结果应该给出排序值.

为了实现这一点,我应该如何构建我的二叉树？

当要删除的节点有两个子节点时,请考虑BST上的删除过程.假设我总是用在其右子树中保持最小键的节点替换它.

问题是:这个程序是可交换的吗？也就是说,删除x然后y与删除第一个y然后x？

我认为答案是否定的,但我找不到反例,也没有找出任何有效的推理.

编辑:

也许我必须更清楚.

考虑以下transplant(node x, node y)过程:将x替换为y(及其子树).所以,如果我想删除一个有两个子节点的节点(比如说x),我用它右边子树中保存最小键的节点替换它:

y = minimum(x.right)
transplant(y, y.right) // extracts the minimum (it doesn't have left child)
y.right = x.right
y.left = x.left
transplant(x,y)

问题是如何证明上述程序不是可交换的.

假设给出了一个级别顺序遍历输出.如何从填充了正确位置的数据构建二叉树？

请注意,我不是试图从给定的遍历输出中绘制树,而是从数组中读取遍历数据,然后通过C中的实际编码填充二叉树.

例如:

设a [] = {A,B,C,D,E,F,G}; //数组中的遍历输出

所以级别顺序树看起来像这样:

            A
           / \ 
          B   C
        / \  / \
       D   E F  G

假设有一个树节点结构,如下所示:

typedef struct node
{
    char data;
    struct node* left;
    struct node* right;
}tree;

现在我正在尝试读取[]值并对此树进行编码,使其看起来像图.有许多级别顺序遍历的例子,但是在二叉树构造的实际编码中找不到任何相关的东西.这有点像"遍历的逆转".

另请注意,这不是功课,但如果有更多人注意到这一点我没有标记问题.:)

为什么二元树要平衡很重要

问题是找出BST中任何路径上是否存在给定的总和.如果路径意味着根到叶子,那么这个问题很容易,或者如果路径意味着从根到叶子的路径的一部分可能不包括根或叶子,则该问题很容易.但这里变得困难,因为路径可能跨越节点的左右子节点.例如,在给定的图中,在圆圈路径上存在132的总和.我怎样才能找到这样一条路径的存在？使用散列来存储节点下的所有可能的总和是不受欢迎的!

我知道,BST不允许重复.例如,如果我有一个单词"RABSAB".

上述字符串的二进制搜索树是:

    R
    /\
   A  S
    \
     B

如果我们想在树中包含重复项,该怎么办？树怎么会改变？我在接受采访时被问到这个问题.

他们让我画画:

1. 二叉树
2. 不平衡的二进制搜索树
3. 没有重复的二叉搜索树
4. 带有重复项的二叉搜索树

任何帮助表示赞赏!

PS:通过绘制相关树帮助我