replace树结构中的根

我有以下树让我们称之为Tree One 。

  1 / \ / \ 2 3 / / 4 

现在我想用2replace根节点。然后上面的树会变成这样的东西。 让我们称之为Tree Two

  2 / \ / \ 4 1 \ \ 3 

我如何才能实现如上所述的数组input？

UPDATE

我已经尝试与Linkedlist。 哪一个在下面，但它不适用于上面的input（即数组）。

  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

我上面的使用喜欢的解决scheme是基于Splay树。 但我需要它的数组input。

Answer 1

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

• 新select的根目录不必是当前根目录的直接子目录（也就是说，你可以直接从状态1进入状态3）。
• 如果新select的根具有左侧和右侧儿童，则其中之一被分配给其以前的家长。

我所做的就是先把它转换成一个结构化的json，然后在那里进行操作。 我用lodash使代码更清洁。

请注意，我的代码有function从您的格式转换为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> 

Answer 2

我不相信有一种方法可以完全独立于数组。 链接列表更适合您的问题。

所以，如果你只能接受数组作为input，你可以做到以下几点：

1. 将您的input数组转换为链接列表。
2. 使用您提供的replaceRootNode函数replace节点。
3. 将链接列表转换回数组。

这里是我做转换数组的代码示例：

 var arr = [2, [1, [3]], [4]]; var tree = { root: null }; arrayToList(arr, tree); console.log(tree); function arrayToList(array, tree){ var node = { data: array[0], left: null, right: null }; if (tree.root == null) { tree.root = node; } if(array[1] instanceof Array) { node.left = arrayToList(array[1], tree); } else { node.left = array[1]; } if(array[2] instanceof Array) { node.right = arrayToList(array[2], tree); } else { node.right = array[2]; } return node; } 

小提琴 （输出在控制台）。

我使用树的Left > Right > Root的后Postorder遍历。 所以它会输出你的树与上面的例子相比。

如果你喜欢首先访问正确的节点，你可以做这个简单的编辑： 小提琴 。 虽然你通常总是访问左前右。

无论如何，那么你可以用你的函数replace你的根节点（还没有尝试过）。

然后，可以执行类似的function将重新排列的树转换回数组。