javascript - 替换树结构中的根

Question

我有以下树，我们称它为 Tree One。

        1
       / \
      /   \
     2     3
    /
   /
  4

现在我想把根 Node 换成2，那么上面的树就会变成这样了。让我们称之为二号树

        2
       / \
      /   \
     4     1
            \
             \
              3

如何为如上所述的数组输入实现上面的内容？

更新

我已经尝试过使用 Linkedlist。然而，在下面，它不适用于上面的输入(即数组)。

    function replaceRootNode(tree, x) {
      var y = x.left;
      x.left = y.right;
      if (y.right) {
        y.right.parent = x;
      }
      y.parent = x.parent;
      if (!x.parent) {
        tree.root = y;
      } else {
        if (x === x.parent.left) {
          x.parent.left = y;
        } else {
          x.parent.right = y;
        }
      }
      y.right = x;
      x.parent = y;
    }

更新 2

我上面使用 likedlist 的解决方案是基于 Splay Tree 的。但我需要它来输入数组。

Answer 1

您的定义不完整，所以我添加了以下定义:

• 新选择的根不必是当前根的直接子 Node (即您可以在示例中直接从状态 1 进入状态 3)。
• 如果新选择的根有左 child 和右 child ，则将其中一个分配给其先前的父 Node 。

我所做的是首先将其转换为结构化的 json 并在那里进行操作。我用了lodash使代码更简洁。

请注意，我的代码具有将您的格式转换为 json 并返回的功能。当您查看代码时，请确保您打开了控制台，此外，您还注释掉了一些更复杂的“树”示例，您也可以尝试它们。

// var tree = [1, [2, [4], [5]], [3]];
var tree = [1, [2, [4]],
  [3]
];
// var tree = [1, [2, [4, [5, [6,[7]]]]], [3]];

var zipTree = _.partial(_.zipObject, ['root', 'left', 'right']);
var toTree = _.flow(zipTree, _.partial(_.pick, _, _.identity));

function toTreeRecurse(data) {
  var result = toTree(data);
  if (_.isArray(result.left)) {
    result.left = toTreeRecurse(result.left);
  }
  if (_.isArray(result.right)) {
    result.right = toTreeRecurse(result.right);
  }
  return (result);
}

function toArrayRecurse(tree) {
  var result = [tree.root];
  if (tree.left) {
    result.push(toArrayRecurse(tree.left));
  }
  if (tree.right) {
    result.push(toArrayRecurse(tree.right));
  }
  return (result);
}

function findValueParent(tree, value) {
  if (!tree) {
    return (null);
  }
  var result;
  if (_.get(tree, 'left.root') === value) {
    return (tree);
  } else if (_.get(tree, 'right.root') === value) {
    return (tree);
  } else if (result = findValueParent(tree.left, value)) {
    return (result);
  } else if (result = findValueParent(tree.right, value)) {
    return (result);
  } else {
    return (null);
  }
}

function setRoot(tree, value) {
  var rootParent = findValueParent(tree, value);
  var newRoot;
  if (rootParent) {
    var fromSide, toSide;
    if (findValueParent(tree.left, value) || (_.get(tree, 'left.root') === value)) {
      fromSide = 'left';
      toSide = 'right';
    } else if (findValueParent(tree.right, value) || (_.get(tree, 'right.root') === value)) {
      fromSide = 'right';
      toSide = 'left';
    }
    newRoot = _.get(rootParent, fromSide);
    if (_.get(newRoot, toSide)) {
      _.set(rootParent, fromSide, _.get(newRoot, toSide));
    } else {
      delete rootParent[fromSide];
    }
    _.set(newRoot, toSide, tree);
    return (newRoot);
  } else {
    console.log('value does not exist');
    return (null);
  }
}
console.log('original: ', JSON.stringify(tree));
console.log('original as json tree: ', JSON.stringify(toTreeRecurse(tree)));
console.log('setting root to 2: ', JSON.stringify(toArrayRecurse(setRoot(toTreeRecurse(tree), 2))));
console.log('setting root to 4: ', JSON.stringify(toArrayRecurse(setRoot(toTreeRecurse(tree), 4))));

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.1/lodash.min.js"></script>

<div>Demo, make sure you open the devtools to see the console print</div>