“排序”树数据结构

最后发布: 2013-03-27 09:13:42


问题

我创建了一个树数据结构,我希望元素排序如下:

      10
     /  \
    5    12
   / \   / \
  3   7 11  18

如果添加的元素的值小于另一个元素的值,则应将其链接到左侧,如果较大,则应链接到右侧。 我的问题是,我无法正确选择排序方法。

class Tree
{
    private class TElement
    {
        public int _value;
        public TElement _left;
        public TElement _right;

        public TElement(int value)
        {
            _value = value;
        }
    }

    private TElement RootElement;

    public void Add(int value)
    {
        TElement newElement = new TElement(value);
        TElement current = new TElement(value);
        current = RootElement;
        if (RootElement == null)
        {
            RootElement = newElement;
            return;
        }

        SortNewElement(RootElement, RootElement, newElement, RootElement);
    }

    private void SortNewElement(TElement left, TElement right, TElement newElement, TElement RootElement)
    {
        if (newElement._value < RootElement._value && RootElement._left == null)
        {
            left._left = newElement;
            return;
        }

        if (newElement._value > RootElement._value && RootElement._right == null)
        {
            right._right = newElement;
            return;
        }


        if (newElement._value < left._value && left._left == null)
        {
            left._left = newElement;
            return;
        }

        if (newElement._value > right._value && right._right == null)
        {
            right._right = newElement;
            return;
        }

        SortNewElement(left._left, right._right, newElement, RootElement);
    }      
}

我知道它不起作用,因为它试图获取null元素的链接节点。

c# data-structures tree
回答

从我可以从您的问题中了解到,您只是想在二进制搜索树中插入一个新节点。 它的有序遍历将是一个排序数组。

您可以通过以下简单的伪代码来实现

   insert_new( Node* node, value)
    {

    if(value > node->value)
    {
       if(node->right != null)
       {
         insert_new(node->right,value);
       }
       else
       {
         node->right = new Node(value);
         return;
       } 
   }
   else
   {
      if(node->left != null)
      {
       insert_new(node->left,value)
      }
      else
      {
       node->left = new Node(value);
       return;          
      } 
   }
}


回答

class element{
public:
int value;
   *element left;
   *element right;

   element(int value)
      value = value;

public add(&element a)
   if (a != null)
      {
      if (left!=null){
            left = a;
      }
      else{
         if (left.value > a.value){
             right = left;
             left= a;
         }
         else{
             right=a;
         }

   }