如何在二叉树中添加节点

Question

<前><代码> (5)根 (3)-----^--------(7) (2)---^----(5) ^-----(8)

我想在此二叉搜索树中添加数据为 5 的节点。请帮忙。

Answer 1

注意：这个答案假设您正在谈论二叉搜索树。

从根开始遍历二叉树：

• 如果新元素小于或等于当前节点，则转到左子树，否则转到右子树并继续遍历

• 如果到达一个节点，则可以在其中不要再深入了，因为没有子树，这是插入新元素的地方

  <前><代码> (5)根
  (3)-----^--------(7)
  (2)---^----(5) ^-----(8)
  (5)--^

你从(5)，然后向左（因为 5 <= 5）到 (3)，然后向右（因为 5 > 3）到 (5)，然后你想要转到左子树（因为 5 <= 5），但是您看到没有子树，因此这是插入新元素 (5) 的位置。

Answer 2

这取决于您是否想要保持二叉树：

• 排序
• 平衡

如果这两个都不是要求，那么添加元素的最快方法是将其作为新根，并使树的其余部分具有其子元素之一

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

：二叉搜索树不应该有重复的值，并且插入过程更复杂，需要遍历树来找到插入点。请参阅此处。

对于自平衡二叉搜索树，它甚至更加复杂，例如可能涉及执行树旋转 。请参阅此处了解更多详细信息。

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