How to add node in binary tree

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

I w开发者_如何学Cant to add node with data 5 in this binary Search tree. Please help.

---

Note: This answer assumes you are talking about a binary search tree.

You traverse the binary tree from the root:

• if your new element is less or equal than the current node, you go to the left subtree, otherwise to the right subtree and continue traversing

• if you arrived at a node, where you can not go any deeper, because there is no subtree, this is the place to insert your new element

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

You start at (5), then go left (since 5 <= 5) to (3), then go right (since 5 > 3) to (5), then you want to go to the left subtree (since 5 <= 5), but you see that there is no subtree, so this is the place to insert your new element (5).

---

It depends on whether you want to keep your binary tree:

• sorted
• balanced

If neither of these are requirements then the fastest way to add an element is to put it as the new root and have the rest of the tree has one of its children:

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

For binary search trees you should not have repeated values and the process for insertion is more complicated and requires traversing the tree to find the insertion point. See here.

For self-balancing binary search trees it is even more complicated and can for example involve performing tree rotations. See here for more details.

---

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

---

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