遞歸二叉樹

Question

基本上我的問題是，我需要一個ADDNODE方法，它的簽名是這樣的：

addNode(Node thisNode, Node toAdd) 

我目前的方法簽名是：

AddRecursively(null, usersInput); 

空（節點），因爲它是我需要將值傳遞迴方法的遞歸方法。 usersInput是一個int。

我很笨，如何做仍然使用遞歸的時候被告知要做的事情。

請注意： 請嘗試以簡單的方式解釋您的代碼，如果可能的話，我在編程方面不是太好。

我的代碼應該工作，因爲它是基於我的舊代碼，它確實工作，但我還沒有測試它，Node findNode已被留下，因爲我應該使用兩個節點，但我很笨怎麼辦這是非常誠實的。

public void AddRecursively(Node findNode, Node findNextNode, int usersInput)//don't need findNode i think 
{ 
    if (root.value == null) 
    { 
     root.value = usersInput; //if no root, make it (everytime it is run it will have no root) 
    } 
    else if (usersInput > root.value && root.right == null) 
    { 
     root.right.value = usersInput; //first right of node 
    } 
    else if (usersInput < root.value && root.left == null) 
    { 
     root.left.value = usersInput; //first left of node 
    } 
    //recursive 
    else if (usersInput > root.right.value && root.right != null && findNextNode == null) 
    { 
     findNextNode = root.right; //setting up recursive right 
    } 
    else if (usersInput < root.left.value && root.left != null && findNextNode == null) 
    { 
     findNextNode = root.left; //setting up recursive left 
    } 
    //adding values before doing recursive 
    else if (usersInput > findNextNode.right.value && findNextNode.right == null) 
    { 
     findNextNode.right.value = usersInput; //if the next right is empty add 
    } 
    else if (usersInput < findNextNode.left.value && findNextNode.left == null) 
    { 
     findNextNode.left.value = usersInput; //if next left is empty add 
    } 
    //recursive, should be able to handle left.left.right for example as findNextNode could be right.right then it could = right.right.left 
    else if (usersInput > findNextNode.right.value && findNextNode.right != null) 
    { 
     findNextNode = findNextNode.right; 
     AddRecursively(null, findNextNode, usersInput); 
    } 
    else if (usersInput < findNextNode.left.value && findNextNode.left != null) 
    { 
     findNextNode = findNextNode.left; 
     AddRecursively(null, findNextNode, usersInput); 
    } 
} 

Answer 1

這不一定是我喜歡這樣做的方式，但爲了回答您的具體問題，我會堅持您提出的簽名。

首先我會asume你有下面的類結構：

class BinaryTree<T> where T: IComparable<T> { 
    private Node root; 

    // .... 

    // The public Add interface (might be different for you) 
    public void Add(T value) { 
     if (this.root == null) { 
      // Handle the special empty case 
      this.root = new Node() { Value = value }; 
     } 
     else { 
      // Just call the private one with the right values 
      this.Add(this.root, new Node() { Value = value }); 
     } 
    } 

    // This is where the recursive magic happens 
    private void Add(Node current, Node toAdd) { 
     // This one comes next... 
    } 

    class Node { 
     public T Value; 
     public Node Left; 
     public Node Right; 
    } 
} 

我使用的是不同類的樹本身Node，因爲它可以更容易對付null節點，如果以後當你決定製作一棵平衡樹（AVL，Red Black等）時，從外部操縱Node實例會容易得多。

此外，通用類型T可能不可爲空，但Node是。請注意，T需要爲IComparable<T>。在你的情況下，int就夠了。

現在，讓我們進入遞歸方法。

// .... 

private void Add(Node current, Node toAdd) { 
    // From here on neither `current.Value` nor `toAdd.Value` are ever null 
    if (toAdd.Value.CompareTo(current.Value) <= 0) { 
     // We go left 
     if (current.Left == null) { 
      current.Left = toAdd; 
     } 
     else { 
      Add(node.Left, toAdd); 
     } 
    } 
    else { 
     // We go right 
     if (current.Right == null) { 
      current.Right = toAdd; 
     } 
     else { 
      Add(node.Right, toAdd); 
     }   
    } 
} 

我認爲就是這樣。

現在，如果你問我，如果我們允許私有Add實現返回添加的節點，那麼可以縮短該方法的時間。

// .... 

private Node Add(Node current, Node toAdd) { 
    if (current == null) { 
     return toAdd; 
    } 

    if (toAdd.Value.CompareTo(current.Value) <= 0) { 
     current.Left = Add(current.Left, toAdd); 
    } 
    else { 
     current.Right = Add(current.Right, toAdd); 
    } 

    return current; 
} 

然後公衆Add也簡單

public void Add(T value) { 
    this.root = Add(this.root, new Node() { Value = value }); 
} 

正如@Iboshuizen說，遞歸允許你說用簡單的語句複雜的事情。

希望它能讓你的老闆高興;）。