0

我在弄清楚如何向我的二叉搜索树中添加或插入节点时遇到了一些麻烦。目前我有以下代码：

public void add(int v) { 
        Node n = new Node(v); 
        if(root==null)
            root = n;   
        else {  
            Node m = root;  
            while(...) { //not sure what to check
                if(v < m.value)
                    m = m.left;
                else
                    m = m.right;
            }
            if(...) //not sure what to check
                m.left = n;
            else
                m.right = n; 

        }   
    }

然后我也想在一定范围内生成n个节点。我知道如何对数组执行此操作，但我不确定如何对 BST 中的节点执行此操作。

public void generate(int n, int range) {

  }
4

3 回答 3

1

当您插入二叉树时，您要一直到找到一个没有相应子节点的节点为止。然后在该位置插入新节点。

至于填充范围中的数字，您可以按照与数组相同的方式生成它们，但您可以使用add方法而不是插入到数组中。

于 2013-08-17T07:00:22.370 回答
0

使用您当前的方法，您将需要一个额外的变量来跟踪父级Node

public void add(int v) { 
        Node n = new Node(v); 
        if(root==null)
            root = n;   
        else {  
            Node m = root,k;  
            while(m!=null) {
                if(v < m.value){
                    k=m;
                    m = m.left;
                 }
                else if(v > m.value){
                    k=m;
                    m = m.right;
                 }else{
                    return; //v already exists
                 }
            }
            if(v < k.value)
                k.left=n;
            else
                k.right=n;
        }   
    }

对于关于范围的第二个问题，正如 DrYap 指出的那样，生成一个范围内的数字，并为每个数字调用 add()

于 2013-08-17T06:59:19.680 回答
0

当向 BST 添加一个值时，你会遍历树，直到找到一个空点并在该点插入一个新节点。

首先我们从退化的情况开始。即，没有节点并且根为空/空。

伪代码：

if root is null then
    root = new node(value);
    return;
end if

所以，我们在这里所做的就是构建树的根节点。它不包含叶节点。

所有后续插入现在都要求我们横穿树。

所以首先我们需要一个起点，它是根节点。然后我们还需要知道我们是否到达了一个可以将新值插入到树中的空白点。这需要跟踪两个变量；一个保存我们正在检查的当前节点，一个保存该节点的父节点。

伪代码：

# initialize tracking variables.
checkNode = root;
parentNode = checkNode;

while checkNode is null do
    parent = checkNode; # want to save this for when we find a spot to store our new value
    if valueOf(checkNode) equals value then return # the value is already stored

    if value < valueOf(checkNode) then
        # the new value is less than the value stored in this node so continue down the left branch
        checkNode = checkNode.left 
    else 
        checkNode = checkNode.right # otherwise continue down the right branch
end while

# at this point checkNode will be null and parent will be set to a node that can store a new node with our value.

if value < valueOf(parent) then
     parent.left = node(value) # store a new node in the left of the found parent node
else 
     parent.right = node(value)

我们正在做的是向下遍历树，将要添加的值与我们正在检查的节点的值进行比较。我们还跟踪我们正在检查的节点的父节点，因为这是我们最终要插入新节点的地方。这是因为我们在 checkNode 为空时结束搜索。

于 2013-08-17T07:32:32.363 回答