标签: binary-tree

我现在正在学习数据结构和算法。

我的讲义有一个使用递归方法实现的二叉搜索树的实现。这是一种优雅的方式，但我的问题是在现实生活中的代码中，我是否应该递归地实现二叉搜索树，如果树的高度/深度数很大，它是否会生成大量调用堆栈。

我知道递归是理解许多数据结构概念的关键概念，但是您会选择在现实生活中使用递归吗？

我的场景是一个包含整数的完美平衡的二叉树。

我已经搜索并找到了许多关于二叉树的最佳/最坏情况的解释。最好的情况是O(1)（在根中找到目标），最坏的情况是O(log(n))（树的高度）。

我几乎没有发现关于计算平均复杂度的信息。我能找到的最佳答案是O(log(n)) - 1，但我想我不太明白（如果正确的话）这个平均情况是如何计算的。

此外，搜索不在树中的整数是否会产生相同的复杂性，我认为会，但任何煽动都值得赞赏。

所以基本上我试图用 10^3 个完全随机数“填充”一个文件，所以我可以稍后将它们添加到二叉搜索树中。这是我目前使用的 populate 函数：

void populateFile(BinarySearchTree b) {
    int random_integer;
    srand( time( NULL ) );
    std::ofstream myfile;
    string line;
    myfile.open ("output.txt");
    myfile << "Writing this to a file: ";
    for(int index=0; index<1000; index++)
    {
        random_integer = (rand()%1000)+1;
        cout << random_integer << endl;
        myfile << random_integer;
    }
    myfile.close();

    int value;
    ifstream file ("output.txt");
    if (file.is_open())
    {
        while ( getline (file,line) )
        {
            value = std::stoi(line);
            b.insert(value);
        }
        myfile.close();
    }

    else cout << "Unable to open file";

}

但是我似乎无法写入文件，我只能在控制台上看到数字然后程序崩溃。

我的第二个问题如下：我想将这些相同的数字添加到二叉搜索树中。我已经有一个类和一个 dd …

考虑n个节点的二叉树.为了举例,请考虑以下树:

     1
   /   \
  2     3
 / \   / \
4   5 6   7
           \
            8

有多少种不同的方法可以从根(顶部)节点开始完全遍历树,只移动到直接连接到已访问过的节点的未访问节点(即我可以从1到2到4但是然后到3)？

所以我一直（到目前为止没有成功）试图让我的红黑树实现与重复一致地工作，但它似乎总是缺少那个小东西，所以我在这里。

我试图让树向一侧倾斜，但它似乎没有适当地平衡（从颜色的角度来看）。我想问一下应该如何向红黑树添加重复项？（显然分开使节点变胖，持有或指向重复的键值）。

不是真的在寻找代码审查，对建议更感兴趣。所以基本上我用于插入和平衡的方法（取自算法简介，第三版）是这些（而旋转很明显）：

创建索引时，我怀疑有一列，与数据节点的物理链接有关。当 2 个“seq_in_index”相同时，它们如何放置在节点中？在这种情况下，索引二叉树的结构如何？

对于这些操作中的每一个，平衡二叉搜索树是否会比平衡二叉树在更快的时间内完成任务？

1. 查找树中最小的项。

我认为平衡 BST 会比平衡二叉树有更快的大时间，因为您可以继续向左遍历并找到最小的项目。我认为它会是 O(log n)。

2. 创建树中小于某个值 v 的所有元素的列表。

对于 2，有人可以向我解释一下哪个会有更快的大时间吗？

我已经能够创建一个证明,表明树中的最大总节点数等于n = 2 ^(h + 1) - 1,逻辑上我知道二叉树的高度是log n(可以绘制它出去看)但是我在构建一个正式的证据时遇到了麻烦,这个证据表明一棵有n片叶子的树至少有"log".我遇到或能够组合的每个证据总是处理完美的二叉树,但我需要适合任何情况的东西.有什么提示可以引导我朝着正确的方向前进

我试图理解使用 2 个堆栈实现后序遍历是多么直观。有人是如何想出它的，它只是一种观察或某种特定的思维方式，可以帮助人们想出这样的方法。如果是，那么请解释如何朝着正确的方向思考。

我一直想知道二叉树的迭代前序遍历（使用堆栈）的空间复杂度是多少。我参考了 Elements of Programming Interviews，他们说

空间复杂度为 O(h)，其中 h 是树的高度，因为除了栈顶之外，栈中的节点对应于从根开始的路径上节点的右孩子.

以下是参考代码：

struct Node{
   int data;
   struct Node* left, right;
}
void printPreOrder(struct Node* root){
  if(!root)
   return ;
  stack<struct Node* > s;
  s.push(root);
  while(!s.empty()){
     struct Node *root_element = s.top();
     cout<<root_element->data<<" ";
     s.pop();
      if(root_element->right){
         s.push(root_element->right);
      }
      if(root_element->left){
         s.push(root_element->left);
      }
     }
     cout<<endl;
  }
  return ;
}

我的直觉

在执行算法时，我观察到堆栈中任何实例的最大条目数可以是 max(num_of_leaves_in_left_subtree+1, num_of_trees_in_right_subtree)。由此我们可以推断，对于高度为 h 的树，最大叶子数可以是 2^h。因此，左子树中的最大树数为 2^(h-1)。因此，堆栈中的最大条目数为 2^(h-1)+1。因此，根据我的说法，上述算法的空间复杂度为 O(2^(log(n)))。