0

请帮助我一直在尝试生成大小为 1024 的随机二叉搜索树,并且元素需要是随机排序集......我可以通过手动添加元素来编写代码来手动创建二叉搜索树,但我'我无法编写一个代码,该代码将生成大小为 1024 的随机平衡二叉树,然后尝试在该树中找到一个密钥......请提前谢谢你......

从评论中编辑添加的代码

是的,这是家庭作业……这就是我目前得到的代码:

using System; 
namespace bst { 
    public class Node { 
        public int value; 
        public Node Right = null; 
        public Node Left = null; 

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

    public class BST { 
        public Node Root = null; 
        public BST() { }

        public void Add(int new_value) 
        { 
            if(Search(new_value)) 
            {
                Console.WriteLine("value (" + new_value + ") already");
            }
            else
            {
                AddNode(this.Root,new_value);
            }
        }
    }
}
4

2 回答 2

2

使用递归。每个分支生成一个新的分支,选择未排序集中的中间项,即中位数。将它放在树中的当前项中。将小于中位数的所有项目复制到另一个数组,将该新数组发送到同一方法的调用。将所有大于中位数的项目复制到另一个数组,将该新数组发送到同一方法的调用。\

平衡树必须有奇数个项目,除非主父节点未填写。您需要确定是否有两个值是中位数,重复项是属于下分支还是上分支。在我的示例中,我将重复项放在上部分支上。

中位数将是相等数量的数字小于和大于数字的数字。1,2,3,3,4,18,29,105,123 在这种情况下,中位数为 4,即使平均值(或平均值)要高得多。

我没有包含确定中位数的代码。

BuildTreeItem(TreeItem Item, Array Set)  
{
  Array Smalls;
  Array Larges;
  Median = DetermineMedian(Set);
  Item.Value = Median;
  if(Set.Count() == 1)
    return;  
  for (int i = 0; int i < Set.Count(); i++)
  {
    if(Set[i] < Median)
    {
      Smalls.new(Set[i]);
    }
    else
    {
      Larges.new(Set[i]);
    }
  }
  Item.Lower = new TreeItem;
  Item.Upper = new TreeItem;
  BuildTreeItem(TreeItem.Lower, Smalls);
  BuildTreeItem(TreeItem.Upper, Larges);
}
于 2011-01-21T00:13:12.457 回答
0

除非它是家庭作业,否则最简单的解决方案是先对数据进行排序,然后使用中间项作为根并向下每半部分下降来构建一棵树。Xaade 提出的方法类似,但由于DetermineMedian 的复杂性而慢得多

另一种选择是实际查看构建平衡树的算法(例如http://en.wikipedia.org/wiki/Red-black_tree),看看它是否符合您的要求。

编辑:删除关于 Xaade 算法速度的错误陈述 - 它实际上与快速排序一样快(n log n - 检查每个递归级别的每个元素,使用 log n 级递归),不知道为什么我估计它更慢。

于 2011-01-21T01:42:40.747 回答