Как добавить узел добавления в двоичном дереве

Question

                   (5)Root
          (3)-------^--------(7)
     (2)---^----(5)           ^-----(8)

Я хочу добавить узел с данными 5 в это двоичное дерево поиска. Пожалуйста, помогите.

Answer 1

Вы пересекаете двоичное дерево от корня:

• если ваш новый элемент меньше или равен текущему узлу, вы переходите к левому поддереву, в противном случае к правому поддереву и продолжаете обход

• если вы прибыли в узел, где вы не можете углубиться глубже, потому что нет поддерева, это место для вставки вашего нового элемента

                 (5)Root
        (3)-------^--------(7)
   (2)---^----(5)           ^-----(8)
          (5)--^
  

Вы начинаете с (5), затем идете влево (с 5 <= 5) до <code>(3), затем идете направо (с 5> 3) до (5), затем вы хотите перейти к левому поддереву (так как 5 <= 5), но вы видите, что нет поддерева, так что это место для вставки вашего нового элемента <code>(5).

Answer 2

Это зависит от того, хотите ли вы сохранить свое двоичное дерево:

• отсортирован
• сбалансирован

Если ни одно из этих требований не является обязательным, то самый быстрый способ добавить элемент - это поместить его в качестве нового корня, чтобы у остального дерева был один из его потомков:

                         (5)
                   (5)----^
          (3)-------^--------(7)
     (2)---^----(5)           ^-----(8)

Для двоичных деревьев поиска у вас не должно быть повторяющихся значений, и процесс вставки является более сложным и требует обхода дерева, чтобы найти точку вставки. Смотри здесь .

Для самобалансирующихся бинарных деревьев поиска это еще более сложно и может, например, включать выполнение поворотов дерева . См. здесь для получения более подробной информации.

Answer 3

/// <summary>
    /// Construct the tree from a pre order traversal
    /// </summary>
    /// <param name="preorderTraversal"></param>
    /// <returns></returns>
    public static TreeNode ConstructTreeFromPreOrderTraversal(int[] preorderTraversal)
    {

        if (null == preorderTraversal || preorderTraversal.Length < 1)
            return null;
        TreeNode root = null;
        int len = preorderTraversal.Length;
        for (int i = 0; i < len; i++)
        {
            TreeNode newNode = new TreeNode();
            newNode.Data = preorderTraversal[i];
            newNode.Left = newNode.Right = null;
            AddNode(ref root, newNode);
        }
        return root;
    }

    /// <summary>
    /// add not in the tree
    /// </summary>
    /// <param name="root"></param>
    /// <param name="newNode"></param>
    private static void AddNode(ref TreeNode root, TreeNode newNode)
    {
        if (root == null)
            root = newNode;
        else if (newNode.Data < root.Data)
        {
            TreeNode left = root.Left;
            AddNode(ref left, newNode);
            root.Left = left;
        }
        else
        {
            TreeNode right = root.Right;
            AddNode(ref right, newNode);
            root.Right = right;
        }
    }

Answer 4

private void Insert(Node node, ref Node tree)
{    
        if (tree == null)                          // Found a leaf?    
        {                                      
             tree = node;                          // Found it! Add the new node as the new leaf.
        }    
        else    
        {        
             int val = string.Compare(node.Key, tree.Key);        // already inserted        
             if (val == 0)
             {            
                  throw new InvalidOperationException("Duplicate key");
             }        
             elseif (val < 0)        
             {            
                  Node left = tree.Left;            
                  Insert(node, ref left);              // Keep moving down the left side.            
                  tree.Left = left;        
             }        
             else        
             {            
                  Node right = tree.Right;         
                  Insert(node, ref right);            // Keep moving down the right side.            
                  tree.Right = right;        
             }    
      }
}