Comment ajouter noeud ajouter dans l'arbre binaire

Question

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

Je veux ajouter noeud avec des données 5 dans ce binaire arbre de recherche. S'il vous plaît aider.

Answer 1

Vous déplacez l'arbre binaire de la racine:

• si votre nouvel élément est inférieur ou égal que le noeud courant, vous allez à la sous-arborescence à gauche, sinon le sous-arbre à droite et continuer traversant

• si vous êtes arrivé à un noeud, où vous ne pouvez pas aller plus loin, car il n'y a pas de sous-arbre, c'est l'endroit idéal pour insérer votre nouvel élément

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

Vous commencez à (5), puis allez à gauche (depuis 5 < = 5) jusqu'à (3), puis allez à droite (depuis 5> 3) jusqu'à (5), puis vous voulez aller à la sous-arborescence de gauche (depuis 5 < = 5), mais vous voyez qu'il n'y a pas de sous-arbre, donc c'est l'endroit où insérer votre nouvel élément (5).

Answer 2

Cela dépend si vous voulez garder votre arbre binaire:

• triés
• équilibré

Si aucun d'entre eux sont des exigences alors le moyen le plus rapide d'ajouter un élément est de mettre comme la nouvelle racine et avoir le reste de l'arbre a un de ses enfants:

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

Pour les arbres de recherche binaire, vous ne devriez pas avoir de valeurs répétées et le processus d'insertion est plus compliqué et nécessite de parcourir l'arbre pour trouver le point d'insertion. Voir here.

Pour les arbres de recherche binaires auto-équilibrés, il est encore plus compliqué et peut par exemple impliquer tree rotations. Voir here pour plus de détails.

Answer 3

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

Answer 4

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