递归二叉树

Question

基本上，我的问题是我需要一个addNode方法，该方法的签名如下：

addNode(Node thisNode, Node toAdd)

我目前的方法签名是：

AddRecursively(null, usersInput);

null(节点)，因为这是一个递归方法，我需要将值传递回该方法。usersInput是一个内部

我不知道如何在仍然使用递归的情况下完成别人告诉我要做的事情。

请注意：如果可能的话，请试着用简单的方式解释你的代码，我不太擅长编程。

我的代码应该可以工作，因为它是基于我的旧代码的，我的代码确实可以工作，但我还没有测试它，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

这不一定是我喜欢的方式，但为了回答您的具体问题，我会坚持您提出的签名。

首先，我假设你有以下类结构：

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、红-黑等)，那么从外部操作Node实例会容易得多。

此外，泛型类型T可能不可以为null，但Node可以为null。请注意，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所说，递归允许你用简单的语句说出复杂的事情。

希望它能让你的老板高兴；)。