分割二叉搜索树

118

阿姆雷德·辛格：

给定一个BST树，我们必须根据输入（N）将其分解为两个子树，其中子树1由小于或等于N的所有节点组成，子树2由大于3的所有节点组成N.

          50
     /        \
     40         60
  /    \        /
 30     45     55
                 \
                  58

输出：

我想出了以下算法，但无法正常工作：

static Node splitTree(Node root, Node root2, int k){
    if(root == null)
        return null;

    while(root != null){
        if(root.data > k)
            root = root.left;
        else if(root.data < k)
            root = root.right;
        else
        {
            root2=root.right;
            root.right=null;
            break;
        }

    }
        return root2;


}

小装饰

您不需要root2参数，因为那是函数的结果，无论传递什么值都将被覆盖。

分割算法通常不仅需要切割边缘（制作两棵树），而且还需要在切割树的更深层次上重复该操作，因为那里可能有子树应附在切割树的位置，发生了。

例如，如果您的树看起来像这样：

                              16  
               +---------------+---------------+
               8                              24
       +-------+-------+               +-------+-------+
       4              12              20              28
   +---+---+       +---+---+       +---+---+       +---+---+
   2       6      10      14      18      22      26      30
 +-+-+   +-+-+   +-+-+   +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
 1   3   5   7   9  11  13  15  17  19  21  23  25  27  29  31

您想用剪切k = 11，那么两棵树看起来像这样：

               8
       +-------+-------+
       4              10
   +---+---+       +---+---+
   2       6       9      11
 +-+-+   +-+-+     
 1   3   5   7      

                              16  
               +---------------+---------------+
              12                              24
               +-------+               +-------+-------+
                      14              20              28
                   +---+---+       +---+---+       +---+---+
                  13      15      18      22      26      30
                                 +-+-+   +-+-+   +-+-+   +-+-+
                                17  19  21  23  25  27  29  31

注意如何切割和替换了多个边：将16-8替换为16-8，将8-12替换为8-12。这可以重复几次，并且对应于在树中找到目标值（位置）的侧向开关（在左右之间）的数量。

建议的代码：

static void setChild(Node node, boolean toLeft, Node child){
    // Assign child node to the indicated direction: left or right
    if (toLeft) {
        node.left = child;
    } else {
        node.right = child;
    }
}

static Node splitTree(Node root, int k){
    Node root2 = null;
    Node parent1 = null;
    Node parent2 = null;
    // Determine at which side of the root we will travel
    boolean toLeft = root != null && k < root.data;

    while (root != null) {
        while (root != null && (k < root.data) == toLeft) {
            parent1 = root;
            root = toLeft ? root.left : root.right;
        }
        setChild(parent1, toLeft, null); // Cut out the edge. root is now detached
        toLeft = !toLeft; // toggle direction
        if (root2 == null) {
            root2 = root; // This is the root of the other tree.
        } else if (parent2 != null) {
            setChild(parent2, toLeft, root); // re-attach the detached subtree
        }
        parent2 = parent1;
        parent1 = null;
    }
    return root2;
}

看到它在repl.it上运行

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。