0

如果有人问过这个问题，请原谅我，但我在搜索时找不到它。所有的搜索结果都是关于遍历二叉树的，就好像一个人正在搜索一个特定的节点一样——因此它最终会下降左或右等等。

但是遍历更新树的大小呢？就像你在底部添加了一个新节点一样，你必须更新每个节点的大小以反映新的树大小。

假设这是原始树并添加 Z：

    D              D
   / \            / \
  A   S   -->    A   S
     /              / \
    N              N   Z
(size = 4)      (size = 5)

所以要更新大小，除非我想错了，否则你必须先更新下面的节点，然后才能更新它上面的节点。正确的？（要更新 D，您必须先更新 S 和 A）

那么，您将如何从根遍历到底部但从底部向上更新？

4

1 回答 1

0

我仍然不确定您存储每个子树大小的用例是什么，但是在每次插入期间很容易保持更新，而无需求助于递归。为简单起见，假设您从以下定义开始：

public static class BSTNode
{
    public BSTNode leftTree = null;
    public BSTNode rightTree = null;
    public int subtreeSize = 1;
    public int value;

    public BSTNode(int valToAdd){
        value = valToAdd;
    }
}

public static class BST
{
    public BSTNode root;

    //public void insert(int valToAdd)
}

在 的实现中insert，我们将从根开始并遍历树以找到添加新值的适当位置。我们可以随时更新每个子树的大小。一个简单的实现可能如下所示：

public void insert(int valToAdd)
{
    if(root == null){
        root = new BSTNode(valToAdd);
        return;
    }

    BSTNode parent = root;
    BSTNode current = root;
    while(current != null){
        parent = current;
        ++current.subtreeSize;
        if(valToAdd <= current.value){
            current = current.leftTree;
        }
        else{
            current = current.rightTree;                
        }
    }

    if(valToAdd <= parent.value){
        parent.leftTree = new BSTNode(valToAdd);
    }
    else{
        parent.rightTree = new BSTNode(valToAdd);
    }
}

在某些情况下，您希望从底部开始更新，例如跟踪子树高度（可能用于重新平衡）。假设BSTNode现在的定义是：

public static class BSTNode
{
    public BSTNode leftTree = null;
    public BSTNode rightTree = null;
    public int height = 0;
    public int value;

    public BSTNode(int valToAdd){
        value = valToAdd;
    }
}

在insert中，使用 a Stack（或任何可以提供 LIFO 语义的东西）来存储新插入节点的祖先。修改我们之前的简单示例：

public void insert(int valToAdd)
{
    if(root == null){
        root = new BSTNode(valToAdd);
        return;
    }

    java.util.Stack<BSTNode> stack = new java.util.Stack<BSTNode>();

    BSTNode parent = root;
    BSTNode current = root;
    while(current != null){
        parent = current;
        stack.push(current);
        if(valToAdd <= current.value){
            current = current.leftTree;
        }
        else{
            current = current.rightTree;                
        }
    }

    if(valToAdd <= parent.value){
        parent.leftTree = new BSTNode(valToAdd);
    }
    else{
        parent.rightTree = new BSTNode(valToAdd);
    }

    int height = 1;
    while(!stack.isEmpty()){
        current = stack.pop();
        current.height = Math.max(height, current.height);
        ++height;
    }
}
于 2014-04-09T19:37:59.353 回答