提问人：daniel blythe 提问时间：11/4/2023 更新时间：11/5/2023 访问量：60
如何编写一个函数来浏览非二叉树？
How to write a function to navigate through a non-binary tree?
问：
我有一个公司组织结构图，我使用'react-organizational-chart'npm包在React / Nextjs中构建。
我希望用户能够使用键盘键、屏幕按钮或两者兼而有之在非二叉树上上/下和左右导航。
例如，用户可能会从“Sarah”>“Michael”>“Robert”>“Emily”>“Daniel”-“Sophie”移动
请看下图的视觉表现。
移动到新节点组时，用户始终希望从该组中的第一个节点开始。
下面是屏幕截图中呈现的数据的示例。
用户还可以返回树上和另一侧。
从“Sarah”5555 开始的函数应如何工作的表示
navigateHierarchy('downKey') // 5556 (Michael Davis's id )
navigateHierarchy('rightKey') // 5560 (Robert Smith's id )
navigateHierarchy('downKey') // 5561 (Emily Wilson's id )
navigateHierarchy('rightKey') // 5561 (Daniel Brown's id )
navigateHierarchy('rightKey') // 5563 (Daniel Brown's id )
const data: IHierarchyData = [
{
name: "Sarah Johnson",
position: "CEO",
email: "[email protected]",
id: "5555",
children: [
{
name: "Michael Davis",
position: "CFO",
email: "[email protected]",
id: "5556",
children: [
{
name: "Sophia Adams",
position: "Finance Manager",
email: "[email protected]",
id: "5557",
children: [],
},
{
name: "William Harris",
position: "Financial Analyst",
email: "[email protected]",
id: "5558",
children: [],
},
{
name: "Oliver Turner",
position: "Accounting Manager",
email: "[email protected]",
id: "5559",
children: [],
},
],
},
{
name: "Robert Smith",
position: "COO",
email: "[email protected]",
id: "5560",
children: [
{
name: "Emily Wilson",
position: "VP of Operations",
email: "[email protected]",
id: "5561",
children: [],
},
{
name: "Daniel Brown",
position: "Director of Production",
email: "[email protected]",
id: "5562",
children: [],
},
{
name: "Sophie Turner",
position: "Director of Logistics",
email: "[email protected]",
id: "5563",
children: [],
},
{
name: "Olivia Lee",
position: "VP of HR",
email: "[email protected]",
id: "5564",
children: [
{
name: "Ethan Miller",
position: "HR Manager",
email: "[email protected]",
id: "5565",
children: [],
},
],
},
],
},
],
},
];
以下是我必须使用 with 和 props 的坐标对象遍历树的早期想法。xy
x将表示您所在的行，并表示该列。y
我尝试编写一个函数，每当用户单击左、右、上或下时，它都会分别增加列或行。
因此，这些键盘点击（向下、向右、向下）最终会得到以下内容，但对于这些数字/坐标，我认为最终出现在“Emily Wilson”上并不是特别容易，甚至不可能
coords = {
x: 2,
y: 1,
}
我对如何解决这个问题感到相当迷茫。
任何帮助，非常感谢。
答：
1赞
Heiko Theißen
11/4/2023
#1
我建议使用 、 和链接来丰富结构，并在执行导航步骤时遵循这些链接。dataupdownleftright
下面的递归函数确保所有根节点（如果不止一个“Sarah Johnson”）也被链接起来进行左/右导航。link
const data = [{
name: "Sarah Johnson",
position: "CEO",
email: "[email protected]",
id: "5555",
children: [{
name: "Michael Davis",
position: "CFO",
email: "[email protected]",
id: "5556",
children: [{
name: "Sophia Adams",
position: "Finance Manager",
email: "[email protected]",
id: "5557",
children: [],
},
{
name: "William Harris",
position: "Financial Analyst",
email: "[email protected]",
id: "5558",
children: [],
},
{
name: "Oliver Turner",
position: "Accounting Manager",
email: "[email protected]",
id: "5559",
children: [],
},
],
},
{
name: "Robert Smith",
position: "COO",
email: "[email protected]",
id: "5560",
children: [{
name: "Emily Wilson",
position: "VP of Operations",
email: "[email protected]",
id: "5561",
children: [],
},
{
name: "Daniel Brown",
position: "Director of Production",
email: "[email protected]",
id: "5562",
children: [],
},
{
name: "Sophie Turner",
position: "Director of Logistics",
email: "[email protected]",
id: "5563",
children: [],
},
{
name: "Olivia Lee",
position: "VP of HR",
email: "[email protected]",
id: "5564",
children: [{
name: "Ethan Miller",
position: "HR Manager",
email: "[email protected]",
id: "5565",
children: [],
}, ],
},
],
},
],
}, ];
function link(node) {
if (node.children[0]) node.down = node.children[0];
for (var i = 0; i < node.children.length; i++) {
node.children[i].up = node;
if (i > 0) {
node.children[i].left = node.children[i - 1];
node.children[i - 1].right = node.children[i];
}
link(node.children[i]);
}
}
link({
children: data
});
var current = data[0];
currentNode.textContent = current.name;
document.addEventListener("keyup", function(event) {
var node;
switch (event.which) {
case 40:
node = current.down;
break;
case 38:
node = current.up;
break;
case 37:
node = current.left;
break;
case 39:
node = current.right;
break;
}
if (node?.name) {
current = node;
currentNode.textContent = current.name;
}
});<span id="currentNode"></span>评论
0赞
daniel blythe
11/5/2023
谢谢你的回答，我认为这也会奏效。
1赞
trincot
11/5/2023
#2
下面是一个将图形作为输入的类，它跟踪它在该树中的位置：Cursor
class Cursor {
#data
#path
#current
constructor(data) {
this.#data = data;
this.#path = [{ children: data }];
this.#current = data[0];
}
get() {
return this.#current;
}
down() {
if (this.#current?.children?.length) {
this.#path.push(this.#current);
this.#current = this.#current.children[0];
}
}
up() {
if (this.#path.length > 1) {
this.#current = this.#path.pop();
}
}
right() {
this.#current = this.#path.at(-1)?.children?.[this.getChildIndex() + 1] ?? this.#current;
}
left() {
this.#current = this.#path.at(-1)?.children?.[this.getChildIndex() - 1] ?? this.#current;
}
getChildIndex() {
if (!this.#path.length) return 0;
let i = this.#path.at(-1).children.indexOf(this.#current);
if (i < 0) throw "Inconsistency";
return i;
}
}
// Example data
const data = [{name: "Sarah Johnson",position: "CEO",email: "[email protected]",id: "5555",children: [{name: "Michael Davis",position: "CFO",email: "[email protected]",id: "5556",children: [{name: "Sophia Adams",position: "Finance Manager",email: "[email protected]",id: "5557",children: [],},{name: "William Harris",position: "Financial Analyst",email: "[email protected]",id: "5558",children: [],},{name: "Oliver Turner",position: "Accounting Manager",email: "[email protected]",id: "5559",children: [],},],},{name: "Robert Smith",position: "COO",email: "[email protected]",id: "5560",children: [{name: "Emily Wilson",position: "VP of Operations",email: "[email protected]",id: "5561",children: [],},{name: "Daniel Brown",position: "Director of Production",email: "[email protected]",id: "5562",children: [],},{name: "Sophie Turner",position: "Director of Logistics",email: "[email protected]",id: "5563",children: [],},{name: "Olivia Lee",position: "VP of HR",email: "[email protected]",id: "5564",children: [{name: "Ethan Miller",position: "HR Manager",email: "[email protected]",id: "5565",children: [],},],},],},],},];
const cursor = new Cursor(data);
// I/O
const [up, left, right, down] = document.querySelectorAll("button");
const out = document.querySelector("span");
const output = () => out.textContent = cursor.get().id;
up.addEventListener("click", () => output(cursor.up()));
left.addEventListener("click", () => output(cursor.left()));
right.addEventListener("click", () => output(cursor.right()));
down.addEventListener("click", () => output(cursor.down()));
output(cursor);<table>
<tr><td></td><td><button>up</button></td></tr>
<tr><td><button>left</button></td><td><span></span></td><td><button>right</button></td></tr>
<tr><td></td><td><button>down</button></td></tr>
</table>评论
0赞
daniel blythe
11/5/2023
绝对太棒了，工作完美。谢谢。
0赞
daniel blythe
11/7/2023
嗨，@trincot，这个解决方案是否遵循我可以做一些阅读的任何类型的设计模式？谢谢。
1赞
trincot
11/7/2023
您可以阅读有关游标的信息，这是数据库中的一个概念。通常，可以使用光标来回导航，或者转到集合的极端之一。但是，由于这里的集合不是一维的，因此此“光标”允许向上/向下和向左/向右移动，而不是通常的下一个/上一个。这也可以称为四向迭代器。游标的实现在这里使用 OOP（面向对象编程）。
1赞
daniel blythe
11/8/2023
太棒了，谢谢！
下一个：打印二叉搜索树的最坏情况运行时间
评论