c# - “排序”树数据结构

Question

我做了一个树数据结构，我希望元素像这样排序：

      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);
    }      
}

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

Answer 1

根据我从您的问题中可以理解的内容，您只是想在二叉搜索树中插入一个新节点。它的中序遍历将是一个排序数组。

您可以通过以下简单的伪代码来做到这一点

   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;          
      } 
   }
}

Answer 2

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;
         }

   }