在二叉樹中交換節點

Question

我想寫一個函數在C＃，它允許我交換二叉樹的兩個節點，但它不能按預期方式工作。

這裏是類與交換方法：

class Node 
{ 
    public int value; 
    public Node parent { get; set; } 
    public Node left { get; set; } 
    public Node right { get; set; } 

    public Node addLeft(int value) 
    { 
     this.left = new Node(value); 
     this.left.parent = this; 
     this.left.left = null; 
     this.left.right = null; 
     return this.left; 
    } 

    public Node addRight(int value) 
    { 
     this.right = new Node(value); 
     this.right.parent = this; 
     this.right.left = null; 
     this.right.right = null; 
     return this.right; 
    } 

    public Node(int value) 
    { 
     this.value = value; 
     this.parent = null; 
     this.left = null; 
     this.right = null; 
    } 

    public Node getRoot() 
    { 
     Node n = this; 
     while(n.parent!=null) 
     { 
      n = n.parent; 
     } 
     return n; 
    } 

    public static void swap(ref Node n1,ref Node n2) 
    { 
     //updating references of n1 and n2 parents 
     if(n1.Equals(n1.parent.left)) //n1 is a left child 
     { 
      n1.parent.left = n2; 
     } 
     else if(n1.Equals(n1.parent.right)) //n1 is a right child 
     { 
      n1.parent.right = n2; 
     } 
     else 
     { 
      throw new Exception("Something is wrong"); 
     } 
     if (n2.Equals(n2.parent.left)) //n2 is a left child 
     { 
      n2.parent.left = n1; 
     } 
     else if (n2.Equals(n2.parent.right)) //n2 is a right child 
     { 
      n2.parent.right = n1; 
     } 
     else 
     { 
      throw new Exception("Something is wrong"); 
     } 
     //updating references of n1 and n2 childs 
     if(n1.left != null) 
     { 
      n1.left.parent = n2; 
     } 
     if (n1.right != null) 
     { 
      n1.right.parent = n2; 
     } 
     if (n2.left != null) 
     { 
      n2.left.parent = n1; 
     } 
     if (n2.right != null) 
     { 
      n2.right.parent = n1; 
     } 
     //Swapping n1 and n2 references 
     Node t_p = n1.parent; 
     Node t_l = n1.left; 
     Node t_r = n1.right; 
     n1.parent = n2.parent; 
     n1.left = n2.left; 
     n1.right = n2.right; 
     n2.parent = t_p; 
     n2.left = t_l; 
     n2.right = t_r; 

    } 
} 

---

這裏是我的主要功能：

static void Main(string[] args) 
    { 
     Node root = new Node(10); 
     Node a = root.addLeft(1); 
     Node b = root.addRight(2); 
     Node c = a.addLeft(3); 
     Node d = a.addRight(4); 
     Node e = b.addLeft(5); 
     Node f = b.addRight(6); 
     Node g = d.addLeft(7); 
     Node h = d.addRight(8); 
     Node.swap(ref a,ref d); 
     Console.WriteLine("Value is: " + root.left.value); 
     Console.WriteLine("Value is: " + root.left.right.value); 
     Console.WriteLine("Root: " + a.getRoot().value); 
     Console.WriteLine("Root: " + d.getRoot().value); 
     Console.Read(); 
    } 

---

的輸出上面的代碼是：

Value is: 4 
Value is: 1 

它掛在第二個Console.WriteLine後，我不明白爲什麼。你能告訴我我做錯了什麼嗎？

---

編輯：

如果我嘗試將節點多次交換時，「有些事情不對」拋出異常。

Answer 1

while (n.parent != null) 

這個條件永遠不會滿足，所以你被困在一個while循環中。

您的交換方法創建一個具有無限祖先樹（父）的節點。如果您沿着.getRoot()的當前節點n行走，則永遠找不到空父節點。

這裏是樹的狀態，我們開始交換

   ((Root(10)) 
      /   \ 
      a(1)   b(2) 
     / \  / \ 
     c(3) d(4) e(5) f(6) 
      / \ 
      g(7) h(8) 

之前，如果你只交換子節點的& d，你最終與父母的循環引用。

對於您的交換方法更類似這樣的應該工作。爲了清楚起見，我留下了詳細的說明。

public static void swap(ref Node A, ref Node B) 
    { 
     var newA = new Node(B.value); 
     var newB = new Node(A.value); 

     newA.left = A.left; 
     newA.right = A.right; 
     newA.parent = A.parent; 

     newB.left = B.left; 
     newB.right = B.right; 
     newB.parent = B.parent; 

     // Fix up parent node for A 
     if (A.parent.left == A) 
     { 
      // A is a left node 
      A.parent.left = newA; 
     } 
     if (A.parent.right == A) 
     { 
      // A is a Right node 
      A.parent.right = newA; 
     } 

     // Fix up parent node for B 
     if (B.parent.left == B) 
     { 
      // B is a left node 
      B.parent.left = newB; 
     } 
     if (B.parent.right == B) 
     { 
      // B is a right node 
      B.parent.right = newB; 
     } 


     if (newA.right == B) 
     { 
      // If B was a right child of A, update reference to newB 
      newA.right = newB; 
     } 
     if (newA.left == A) 
     { 
      // If B was a left child of A, update reference to newB 
      newA.left = newB; 
     } 

     if (newB.right == A) 
     { 
      // If A was a right child of B, update reference to newA 
      newB.right = newA; 
     } 
     if (newB.left == A) 
     { 
      // If A was a left child of B, update reference to newA 
      newA.left = newB; 
     } 

     // Update child references to be orphaned to point to new parents for A 
     A.left.parent = newA; 
     A.right.parent = newA; 

     // Update child references to be orphaned to point to new parents for A 
     B.left.parent = newB; 
     B.right.parent = newB; 

     // Final Swap to update ref types 
     A = newA; 
     B = newB; 

    } 

希望得到的狀態交換

  ((Root(10)) 
     /   \ 
     d(4)   b(2) 
    / \  / \ 
    c(3) a(1) e(5) f(6) 
     / \ 
     g(7) h(8) 

這裏後，在控制檯上運行一些快速&骯髒的驗證碼。我沒有檢查所有可能的情況，但它現在似乎更新了這種情況下的所有相關節點。

static void Main(string[] args) 
    { 
     var root = new Node(10); 
     var a = root.addLeft(1); 
     var b = root.addRight(2); 
     var c = a.addLeft(3); 
     var d = a.addRight(4); 
     var e = b.addLeft(5); 
     var f = b.addRight(6); 
     var g = d.addLeft(7); 
     var h = d.addRight(8); 
     Node.swap(ref a, ref d); 

     if (root.left.value != 4) 
      throw new ApplicationException("New Root --> left --> value != 4 as expected"); 
     Console.WriteLine("New root --> left node has correct value of 4"); 

     if ((root.left.right.parent != root.left)) 
      throw new Exception("and root --> left --> right has incorrect parent"); 
     Console.WriteLine("Root --> left --> right has the correct parent"); 

     if (root.left.right.value != 1) 
      throw new ApplicationException("New Root --> left --> right --> value did not equal 1."); 
     Console.WriteLine("New Root --> Left --> right has the correct value of 1"); 

     if (root.left.right.left.value != 7) 
      throw new ApplicationException("New Root --> left --> right --> left --> value was not 7 as expected."); 
     Console.WriteLine("New Root --> left --> right --> left.value had a value of 7 as expected"); 

     if (root.left.right.left.parent != root.left.right) 
      throw new ApplicationException("New Root --> left --> right --> left --> parent was not root --> left --> right as expected"); 
     Console.WriteLine("New Root --> Left --> right --> left has the correct value of 7 and expected parent"); 


     Console.Read(); 
    } 

Answer 2

如果我理解你的交換功能應該做的，應該是這樣簡單：

public static void swap(Node n1, Node n2) 
    { 
     Node left1 = n1.left; 
     Node left2 = n2.left; 
     Node right1 = n1.right; 
     Node right2 = n2.right; 
     Node parent1 = n1.parent; 
     Node parent2 = n2.parent; 

     n1.left = left2; 
     n2.left = left1; 

     n1.right = right2; 
     n2.right = right1; 

     n1.parent = parent2; 
     n2.parent = parent1; 
    } 

我認爲你需要做的是簡單交換N1的左側和右側與N2的左和右。因爲它是一個引用類型而不是值類型，所以不需要ref。

Answer 3

請看看這條線：如果N2是N1的右子，因爲在這種情況下

if (n1.right != null) 
{ 
    n1.right.parent = n2; 
} 

，n1.right是n2，所以n1.right.parent = n2實際上是n2.parent = n2這將導致循環。

要解決此問題，您必須先製作節點的副本，然後替換它們，或嘗試自動和獨立地進行這兩種交換。