我正在尝试学习 C# 中数据算法的基础知识,并且在实现以下二叉搜索树添加过程中时,我陷入了理解以下内容的困境:调用 tree1.add 时(20);
方法,在 while
循环的第一次迭代中,current.Data
的值为 50
且在循环的第二次迭代中,相同 current.Data
的值更改为 40。
为什么第一次迭代后current.Data
的值没有停留在50的值以及current.Data
接收值的过程是怎样的40?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinarySearchTree
{
public class Node
{
public int Data;
public Node LeftChild;
public Node RightChild;
}
public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}
public void add(int data)
{
Node newNode = new Node();
newNode.Data = data;
if (root == null)
{
root = newNode;
}
else
{
Node current = root;
Node parent;
while (true)
{
parent = current;
if (data < current.Data)
{
current = current.LeftChild;
if (current == null)
{
parent.LeftChild = newNode;
break;
}
}
else
{
current = current.RightChild;
if (current == null)
{
parent.RightChild = newNode;
break;
}
}
}
}
}
}
class Program
{
static void Main(string[] args)
{
BinarySearchTree tree1 = new BinarySearchTree();
tree1.add(50);
tree1.add(40);
tree1.add(60);
tree1.add(20);
tree1.add(45);
tree1.add(55);
tree1.add(65);
Console.ReadLine();
}
}
}
最佳答案
答案就在这里:
while (true)
{
parent = current;
if (data < current.Data)
{
current = current.LeftChild; // THIS LINE
if (current == null)
{
parent.LeftChild = newNode;
break;
}
}
如您所见,当前正在被重估,现在它是它自己的左“子”。在前 3 次 add
用法之后,树应如下所示:
50
/ \
40 60
所以第一次迭代 - 当前是 50 ,第二次迭代,它向左移动(BST 的定义)并变成 40 。下一次迭代 current 将包含 NULL
,(40 的左 child )并将被放置在 BST 内。
关于c# - 关于二叉搜索树实现的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52137434/