如何添加附加節點在二叉樹

Question

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

我想在這二叉搜索樹添加數據5節點。請幫忙。

Answer 1

您從根遍歷二叉樹：

• 如果你的新元素是小於或大於當前節點平等的，你去左子樹，否則的右子樹，並繼續遍歷

• ，如果你到了一個節點，在那裏你不能去任何更深，因爲沒有樹，這是插入新元素的地方

     (5)Root 
       (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) 

對於二分搜索樹，您不應該有重複的值，並且插入過程更加複雜，並且需要遍歷樹來查找插入點。請參閱here。

對於自平衡二叉搜索樹，它更加複雜，例如可能涉及執行tree rotations。有關更多詳細信息，請參閱here。

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