二叉树到 HTML 列表
Binary Tree to HTML list
我有一个二叉树，我想将其转换为嵌套的 HTML 无序列表。
我有一个函数正在尝试修改以完成任务。
我正在尝试以下方法（运行 输出片段）：
此方法在 BinaryTreeClass 中
inOrderTraverseHtml(start = this.rootPtr) {
if (!start.isLeaf())
{
this.html+="<ul>"
}
else
{
this.html+="<li>"
} // end if
if (start.getLeftChild() !== null)
{
this.inOrderTraverseHtml(start.getLeftChild());
}; // end if
this.html+=`<a href="#">${start.getItem().value}</a>`;
if (start.getRightChild() !== null)
{
this.inOrderTraverseHtml(start.getRightChild());
}; // end if
if (!start.isLeaf())
{
this.html+="</ul>"
}
else
{
this.html+="</li>"
} // end if
} // end inOrderTraverseHtml
这不会创建正确的列表项。我的 ul 太多了。
该片段包含我的完整代码（包含 ES6）
/**
* This is the Node class
* Each item has a setter and getter
*/
class Node {
constructor(item = null, id = null, leftChild = null, rightChild = null) {
this.id = id;
this.item = item;
this.leftChildPtr = leftChild;
this.rightChildPtr = rightChild;
}
setItem(item) {
this.item = item;
}
getItem() {
return this.item;
}
setId(id) {
this.id = id;
}
getId() {
return this.id;
}
isLeaf() {
return this.leftChildPtr === null && this.rightChildPtr === null;
}
getLeftChild() {
return this.leftChildPtr;
}
getRightChild() {
return this.rightChildPtr;
}
setRightChild(rightPtr) {
this.rightChildPtr = rightPtr;
}
setLeftChild(leftPtr) {
this.leftChildPtr = leftPtr;
}
}
/**
* This is the MathModel class
* Each item has a setter and getter
* This gets inserted into the nodes
*/
class MathModel {
constructor(type = "Operator", value = "+") {
this.type = type;
this.value = value;
}
Type() {
return this.type;
}
setType(new_type) {
this.type = new_type;
}
Value() {
return this.value;
}
setValue(new_value) {
this.value = new_value;
}
}
/**
* This is the BinaryNodeTree class
* This is an ADT for a unbalenced binary tree
* The ids for nodes will be phased out or at least be given a better index
* for now I used it for an html canvas
*/
class BinaryNodeTree {
constructor() {
this.rootPtr = null;
this.idRange = [
"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
]
this.ids = [];
this.output = "";
this.html = "";
}
setRoot(type, value) {
let id = this.createId();
this.ids.push(id);
let newNode = new Node(new MathModel(type, value), id);
this.rootPtr = newNode;
}
getRoot() {
return this.rootPtr;
}
createId(len = 6) {
let string = "";
const rangeLength = this.idRange.length;
for (let i = len; i--;) {
string += this.idRange[Math.floor(Math.random() * rangeLength)]
}
return string;
} // createId
getHeightHelper(subTreePtr = new Node()) {
if (subTreePtr === null || subTreePtr === new Node()) {
return 0;
} else {
let a = this.getHeightHelper(subTreePtr.getLeftChild());
let b = this.getHeightHelper(subTreePtr.getRightChild());
let max = 0;
if (a > b) {
max = a;
} else {
max = b;
}
return 1 + max;
}
} // end getHeightHelper
getNumberOfNodesHelper(subTreePtr = new Node()) {
if (subTreePtr === null || subTreePtr === new Node()) {
return 0;
} else if (subTreePtr.isLeaf()) {
return 0;
} else if (subTreePtr.getLeftChild() === null && subTreePtr.getRightChild() !== null || subTreePtr.getLeftChild() !== null && subTreePtr.getRightChild() === null) {
return 1;
} else {
return 2;
}
} // end getNumberOfNodesHelper
/**
* This will be an inorder traverse of the tree to find a node
* @param {function} cb
* @param {Node} treePtr
* @param {*} target
*/
findNodeInOrder(cb, treePtr = this.rootPtr, targetId) {
if (treePtr === null) {
return null;
} else if (treePtr.id === targetId) {
return cb(treePtr);
} else {
this.findNodeInOrder(cb, treePtr.getLeftChild(), targetId);
this.findNodeInOrder(cb, treePtr.getRightChild(), targetId);
}
} // end findNodeInOrder
inOrderTraverse(cb, treePtr = this.rootPtr, parent = null) {
if (treePtr !== null) {
this.inOrderTraverse(cb, treePtr.getLeftChild(), treePtr);
let Item = treePtr.getItem();
cb(Item, treePtr.id, treePtr, parent);
this.inOrderTraverse(cb, treePtr.getRightChild(), treePtr);
}
} // end inOrderTraverse
toString() {
this.output = "";
this.inOrderTraversePrint(this.rootPtr)
return this.output;
}
toHTML() {
this.html = `<div class="tree">`;
this.inOrderTraverseHtml(this.rootPtr)
this.html += "</div>";
return this.html;
}
inOrderTraversePrint(start = this.rootPtr) {
if (!start.isLeaf()) {
// console.log("(");
this.output += "("
}
if (start.getLeftChild() !== null) {
this.inOrderTraversePrint(start.getLeftChild());
}; // end if
// console.log(start.getItem().value);
this.output += start.getItem().value;
if (start.getRightChild() !== null) {
this.inOrderTraversePrint(start.getRightChild());
}; // end if
if (!start.isLeaf()) {
// console.log(")");
this.output += ")";
}
} // end inOrderTraversePrint
inOrderTraverseHtml(start = this.rootPtr) {
if (!start.isLeaf()) {
this.html += "<ul>"
} else {
this.html += "<li>"
} // end if
if (start.getLeftChild() !== null) {
this.inOrderTraverseHtml(start.getLeftChild());
}; // end if
this.html += `<a href="#">${start.getItem().value}</a>`;
if (start.getRightChild() !== null) {
this.inOrderTraverseHtml(start.getRightChild());
}; // end if
if (!start.isLeaf()) {
this.html += "</ul>"
} else {
this.html += "</li>"
} // end if
} // end inOrderTraverseHtml
preOrderTraverse(cb, treePtr = this.rootPtr) {
if (treePtr !== null) {
let Item = treePtr.getItem();
cb(Item, treePtr.id);
this.inOrderTraverse(cb, treePtr.getLeftChild());
this.inOrderTraverse(cb, treePtr.getRightChild());
}
} // end preOrderTraverse
postOrderTraverse(cb, treePtr = this.rootPtr) {
if (treePtr !== null) {
this.inOrderTraverse(cb, treePtr.getLeftChild());
this.inOrderTraverse(cb, treePtr.getRightChild());
let Item = treePtr.getItem();
cb(Item, treePtr.id);
}
} // end postOrderTraverse
addLeft(treePtr = new Node(), newItem) {
let id = this.createId();
while (this.ids.indexOf(id) !== -1) {
id = this.createId();
}
let newNode = new Node(newItem, id);
if (treePtr.getLeftChild() !== null) {
let tempPtr = treePtr.getLeftChild();
newNode.setLeftChild(tempPtr);
treePtr.setLeftChild(newNode);
} else {
treePtr.setLeftChild(newNode);
}
} // end addLeft
addRight(treePtr = new Node(), newItem) {
let id = this.createId();
while (this.ids.indexOf(id) !== -1) {
id = this.createId();
}
let newNode = new Node(newItem, id);
if (treePtr.getRightChild() !== null) {
let tempPtr = treePtr.getRightChild();
newNode.setRightChild(tempPtr);
treePtr.setRightChild(newNode);
} else {
treePtr.setRightChild(newNode);
}
} // end addRight
removeFromIdsHelper(id) {
let index = this.ids.indexOf(id);
this.ids.splice(index, 1);
} // end removeFromIdsHelper
removeRight(treePtr = new Node(), newItem) {
this.removeFromIdsHelper(treePtr.getRightChild().id);
treePtr.setRightChild(null)
// todo: handle existing nodes in children
} // end removeRight
removeLeft(treePtr = new Node(), newItem) {
this.removeFromIdsHelper(treePtr.getLeftChild().id);
treePtr.setLeftChild(null)
// todo: handle existing nodes in children
} // end removeLeft
}
/**
* This is the implementation of the Abstract data type
*/
let tree = new BinaryNodeTree();
function handleCreateClick() {
$("[data-action=start]").off().on("click", function() {
tree.setRoot("Operator", "+");
tree.addLeft(tree.getRoot(), new MathModel("Operator", "-"))
tree.addRight(tree.getRoot(), new MathModel("Number", 20))
tree.addLeft(tree.getRoot().getLeftChild(), new MathModel("Operator", "/"))
tree.addRight(tree.getRoot().getLeftChild(), new MathModel("Number", 60))
tree.addLeft(tree.getRoot().getLeftChild().getLeftChild(), new MathModel("Number", 75))
tree.addRight(tree.getRoot().getLeftChild().getLeftChild(), new MathModel("Number", 60))
console.log("Tree created", "Uncomment line 299 to log it.");
// console.log(tree);
});
}
function handleDrawClick() {
$("[data-action=draw]").off().on("click", function() {
console.log(tree.toString());
$(".output").html(tree.toHTML())
});
}
function invokes() {
handleCreateClick();
handleDrawClick();
}
$(document).ready(() => {
invokes();
})
body {
height: 1000px;
}
<link href="https://stackpath.bootstrapcdn.com/bootstrap/4.1.0/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-9gVQ4dYFwwWSjIDZnLEWnxCjeSWFphJiwGPXr1jddIhOegiu1FwO5qRGvFXOdJZ4" crossorigin="anonymous">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="container">
<div class="row">
<div class="col-xs-12">
<h1>TREE</h1>
<ul>
<li>The Node class starts on line 5</li>
<li>The Math Model class starts on line 45</li>
<li>The Binary Tree class starts on line 69
<ul>
<li>toHTML() starts on line 168</li>
<li>toHTML() calls inOrderTraverseHtml() which is on line 182</li>
<li>This gets called from the implementation on the <span class="btn btn-sm btn-info">Draw</span> event on line 302</li>
</ul>
</li>
<li>The implementation of the Abstract data type starts in JS on line 269</li>
<li>Uncomment line 307 to view the tree</li>
</ul>
<h2>To Start</h2>
<ol>
<li>Click start</li>
<li>Click draw</li>
</ol>
</div>
</div>
<hr/>
<div class="row">
<div class="col-xs-12">
<div class="btn-group">
<div class="btn btn-primary" data-action="start">Start!</div>
<div class="btn btn-info" data-action="draw">Draw!</div>
</div>
</div>
<div class="col-xs-12">
<div class="output"></div>
</div>
</div>
</div>
编辑
我正在尝试创建在 this codeplayer tutorial
中看到的标记
编辑 2
我正在包含一个示例，说明我希望输出的外观如何。
<div class="tree">
<ul>
<li>
<a href="#">Parent</a>
<ul>
<li>
<a href="#">Child</a>
<ul>
<li>
<a href="#">Grand Child</a>
</li>
</ul>
</li>
<li>
<a href="#">Child</a>
<ul>
<li><a href="#">Grand Child</a></li>
<li>
<a href="#">Grand Child</a>
<ul>
<li>
<a href="#">Great Grand Child</a>
</li>
<li>
<a href="#">Great Grand Child</a>
</li>
<li>
<a href="#">Great Grand Child</a>
</li>
</ul>
</li>
<li><a href="#">Grand Child</a></li>
</ul>
</li>
</ul>
</li>
</ul>
所以我向 BinaryNodeTree 添加了一个 class 扩展。它在下面并且可以按我需要的方式工作。
class BinaryNodeTreeToHTML extends BinaryNodeTree {
constructor(rootPtr, className = "tree-html") {
super(rootPtr);
this.html = [];
this.rootPtr = rootPtr;
this.className = className;
}
createContainer() {
const _ = this;
return new $("<div />", {
"class": _.className
});
}
createListItem(type, value, id, parentId) {
const _ = this;
return $("<li />", {
id,
"data-parent_id": parentId,
"data-type": type,
"data-value": value,
html: _.createAnchor(type, value)
});
}
createAnchor(type, value) {
return $("<a />", {
href: "#",
"data-type": type,
text: value
});
}
createUnorderedList(parent = "root") {
return $("<ul />", {
"data-parent": parent
})
}
Start(outputClassName) {
const _ = this;
console.log(this.Root);
const $output = $(`.${outputClassName}`).eq(0);
const $container = this.createContainer();
let $main_ul = _.createUnorderedList();
$container.append($main_ul);
$output.append($container);
console.log(_.html);
this.inOrderTraverse((Item, Id, Pointer, Parent) => {
if (Parent !== null) {
let $new_item = _.createListItem(Item.Type, Item.Value, Id, Parent.Id);
$main_ul.append($new_item);
} else {
let $new_item = _.createListItem(Item.Type, Item.Value, Id, "root");
$main_ul.append($new_item);
}
})
for(let obj of $main_ul.find("li")){
let $obj = $(obj);
if($obj.data().parent_id !== "root"){
let $parent = $("#"+$obj.data().parent_id);
if($parent.find("[data-parent="+$parent.attr("id")+"]").length > 0){
let $ul = $parent.find("[data-parent="+$parent.attr("id")+"]")
$ul.append($obj);
}else{
$parent.append(_.createUnorderedList($parent.attr("id")).append($obj))
}
}
}
return $container;
}
};
我一直在思考这个问题。我很高兴你想出了对你有用的东西。我仍然没有尝试通过您的代码工作。对于我有限的注意力来说，实在是太多了。
但潜在的问题让我感兴趣，我有一个从头开始编写的非常不同的解决方案。
更简单的树
我们从更简单的树结构开始。
const node = (val, left, right) => ({val, left, right})
const preorder = (before, after, node) =>
[before(node.val)]
.concat(node.left ? preorder(before, after, node.left) : [])
.concat(node.right ? preorder(before, after, node.right) : [])
.concat(after(node.val))
问题似乎需要 preorder 遍历，而不是 inorder 遍历。如果我们想要 inorder 遍历，这很简单：
const inorder = (fn, node) =>
(node.left ? inorder(fn, node.left) : [])
.concat(fn(node.val))
.concat(node.right ? inorder(fn, node.right) : [])
请注意，这些遍历只是将每个节点上的函数调用结果收集到一个数组中。为了处理您希望 HTML 个节点在我们的预购版本中相互包装这一事实，我们有单独的 before 和 after 函数。我们稍后会用到它。
像这样构建的树可以非常简单：
node(
'+',
18,
node('*', 4, 6)
)
这会生成这样的 object：
{
val: "+",
left: 18,
right: {
val: "*",
left: 4,
right: 6
}
}
或者如果你愿意，你可以这样做
node(
node('+'),
node(18),
node('*', node(4), node(6))
)
看起来更像这样：
{
val: {
val: "+",
left: undefined,
right: undefined
},
left: {
val: 18,
left: undefined,
right: undefined
},
right: {
val: "*",
left: {
val: 4,
left: undefined,
right: undefined
},
right: {
val: 6,
left: undefined,
right: undefined
}
}
}
如果你打算这样做，你可能更喜欢这个稍微复杂一点的 node:
const node = (val, left, right) =>
Object.assign({val}, left ? {left} : {}, right ? {right} : {})
删除那些 undefineds，给你留下类似
的输出
{
val: {
val: "+"
},
left: {
val: 18
},
right: {
val: "*",
left: {
val: 4
},
right: {
val: 6
}
}
}
节点类型
对于这个问题，我们要考虑两种不同类型的节点，operators 和 numbers。我们创建了两个简单的函数来包装它们：
const operator = (value) => ({type: 'op', value})
const number = (value) => ({type: 'num', value})
请注意，这些类型和上面的 node/tree 函数比您从 OO 语言移植过来要简单得多。 Javascript 是一种更高级的语言，它在很多方面都比 Java/C++/C#/etc.
更简单
示例数据
使用这些节点类型，我们可以像这样创建请求的树：
const myTree = node(
operator('+'),
node(
operator('-'),
node(
operator('/'),
node(number(60)),
node(number(75)),
),
node(number(60))
),
node(number(20))
)
这个问题是以更零碎的方式构建的。我们可以随心所欲地这样做，通过 myTree.left.left.right 等选择器访问节点，并为它们的 left、right 和 val 属性赋值。在任何动态情况下，我们可能都必须这样做。但是如果我们把整个结构放在前面，那就更干净了。
HTML代
我们的 preorder 函数访问每个节点两次，一次在 children（如果有）之前，一次在它们之后。所以我猜它不是真正的 preorder，而是 postorder 的组合。但这适用于我们想要做 before-and-after HTML 片段的 use-case。
const toHtml = (tree) => `<div class='tree'><ul>` + preorder(
node => node.type === 'op'
? `<li><a class="${node.type}" href="#">${node.value}</a><ul>`
: `<li><a class="${node.type}" href="#">${node.value}</a></li>`,
node => node.type === 'op'
? `</ul></li>`
: ``,
tree
).join('') + `</ul></div>`
这是针对我们的问题的，它在提供给 preorder 的前后函数中生成标记，加入结果数组，并将其包装在请求的 <div> 标记中.我们将 CSS 类 添加到标记中，以防有帮助。
用法
把这些放在一起，我们得到
toHtml(myTree)
这将生成类似
的内容
<div class='tree'>
<ul>
<li>
<a class="op" href="#">+</a>
<ul>
<li>
<a class="op" href="#">-</a>
<ul>
<li>
<a class="op" href="#">/</a>
<ul>
<li>
<a class="num" href="#">60</a>
</li>
<li>
<a class="num" href="#">75</a>
</li>
</ul>
</li>
<li>
<a class="num" href="#">60</a>
</li>
</ul>
</li>
<li>
<a class="num" href="#">20</a>
</li>
</ul>
</li>
</ul>
</div>
（虽然没有花哨的缩进。）
演示
我们可以在这段代码中看到这一切是如何协同工作的：
// Binary Tree Implementation
const node = (val, left, right) => ({val, left, right})
const preorder = (before, after, node) =>
[before(node.val)]
.concat(node.left ? preorder(before, after, node.left) : [])
.concat(node.right ? preorder(before, after, node.right) : [])
.concat(after(node.val))
// Node types
const operator = (value) => ({type: 'op', value})
const number = (value) => ({type: 'num', value})
// HTML Generation
const toHtml = (tree) => `<div class='tree'><ul>` + preorder(
node => node.type === 'op'
? `<li><a class="${node.type}" href="#">${node.value}</a><ul>`
: `<li><a class="${node.type}" href="#">${node.value}</a></li>`,
node => node.type === 'op'
? `</ul></li>`
: ``,
tree
).join('') + `</ul></div>`
// Sample Data
const myTree = node(
operator('+'),
node(
operator('-'),
node(
operator('/'),
node(number(60)),
node(number(75)),
),
node(number(60))
),
node(number(20))
)
// Usage
console.log(toHtml(myTree))
总结
这并没有回答您关于为什么您的代码无法运行的基本问题，但它提供了我认为在 Javascript 中处理树木的更简单的解决方案，并创建了一种构建输出的方法你正在寻找一个。
Javascript 至少和 Object-Oriented 一样是一种函数式语言。这里的技术相当实用，使用简单、纯函数。我相信他们会制作出更简洁的程序。
我有一个二叉树，我想将其转换为嵌套的 HTML 无序列表。
我有一个函数正在尝试修改以完成任务。
我正在尝试以下方法（运行 输出片段）：
此方法在 BinaryTreeClass 中
inOrderTraverseHtml(start = this.rootPtr) {
if (!start.isLeaf())
{
this.html+="<ul>"
}
else
{
this.html+="<li>"
} // end if
if (start.getLeftChild() !== null)
{
this.inOrderTraverseHtml(start.getLeftChild());
}; // end if
this.html+=`<a href="#">${start.getItem().value}</a>`;
if (start.getRightChild() !== null)
{
this.inOrderTraverseHtml(start.getRightChild());
}; // end if
if (!start.isLeaf())
{
this.html+="</ul>"
}
else
{
this.html+="</li>"
} // end if
} // end inOrderTraverseHtml
这不会创建正确的列表项。我的 ul 太多了。
该片段包含我的完整代码（包含 ES6）
/**
* This is the Node class
* Each item has a setter and getter
*/
class Node {
constructor(item = null, id = null, leftChild = null, rightChild = null) {
this.id = id;
this.item = item;
this.leftChildPtr = leftChild;
this.rightChildPtr = rightChild;
}
setItem(item) {
this.item = item;
}
getItem() {
return this.item;
}
setId(id) {
this.id = id;
}
getId() {
return this.id;
}
isLeaf() {
return this.leftChildPtr === null && this.rightChildPtr === null;
}
getLeftChild() {
return this.leftChildPtr;
}
getRightChild() {
return this.rightChildPtr;
}
setRightChild(rightPtr) {
this.rightChildPtr = rightPtr;
}
setLeftChild(leftPtr) {
this.leftChildPtr = leftPtr;
}
}
/**
* This is the MathModel class
* Each item has a setter and getter
* This gets inserted into the nodes
*/
class MathModel {
constructor(type = "Operator", value = "+") {
this.type = type;
this.value = value;
}
Type() {
return this.type;
}
setType(new_type) {
this.type = new_type;
}
Value() {
return this.value;
}
setValue(new_value) {
this.value = new_value;
}
}
/**
* This is the BinaryNodeTree class
* This is an ADT for a unbalenced binary tree
* The ids for nodes will be phased out or at least be given a better index
* for now I used it for an html canvas
*/
class BinaryNodeTree {
constructor() {
this.rootPtr = null;
this.idRange = [
"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
]
this.ids = [];
this.output = "";
this.html = "";
}
setRoot(type, value) {
let id = this.createId();
this.ids.push(id);
let newNode = new Node(new MathModel(type, value), id);
this.rootPtr = newNode;
}
getRoot() {
return this.rootPtr;
}
createId(len = 6) {
let string = "";
const rangeLength = this.idRange.length;
for (let i = len; i--;) {
string += this.idRange[Math.floor(Math.random() * rangeLength)]
}
return string;
} // createId
getHeightHelper(subTreePtr = new Node()) {
if (subTreePtr === null || subTreePtr === new Node()) {
return 0;
} else {
let a = this.getHeightHelper(subTreePtr.getLeftChild());
let b = this.getHeightHelper(subTreePtr.getRightChild());
let max = 0;
if (a > b) {
max = a;
} else {
max = b;
}
return 1 + max;
}
} // end getHeightHelper
getNumberOfNodesHelper(subTreePtr = new Node()) {
if (subTreePtr === null || subTreePtr === new Node()) {
return 0;
} else if (subTreePtr.isLeaf()) {
return 0;
} else if (subTreePtr.getLeftChild() === null && subTreePtr.getRightChild() !== null || subTreePtr.getLeftChild() !== null && subTreePtr.getRightChild() === null) {
return 1;
} else {
return 2;
}
} // end getNumberOfNodesHelper
/**
* This will be an inorder traverse of the tree to find a node
* @param {function} cb
* @param {Node} treePtr
* @param {*} target
*/
findNodeInOrder(cb, treePtr = this.rootPtr, targetId) {
if (treePtr === null) {
return null;
} else if (treePtr.id === targetId) {
return cb(treePtr);
} else {
this.findNodeInOrder(cb, treePtr.getLeftChild(), targetId);
this.findNodeInOrder(cb, treePtr.getRightChild(), targetId);
}
} // end findNodeInOrder
inOrderTraverse(cb, treePtr = this.rootPtr, parent = null) {
if (treePtr !== null) {
this.inOrderTraverse(cb, treePtr.getLeftChild(), treePtr);
let Item = treePtr.getItem();
cb(Item, treePtr.id, treePtr, parent);
this.inOrderTraverse(cb, treePtr.getRightChild(), treePtr);
}
} // end inOrderTraverse
toString() {
this.output = "";
this.inOrderTraversePrint(this.rootPtr)
return this.output;
}
toHTML() {
this.html = `<div class="tree">`;
this.inOrderTraverseHtml(this.rootPtr)
this.html += "</div>";
return this.html;
}
inOrderTraversePrint(start = this.rootPtr) {
if (!start.isLeaf()) {
// console.log("(");
this.output += "("
}
if (start.getLeftChild() !== null) {
this.inOrderTraversePrint(start.getLeftChild());
}; // end if
// console.log(start.getItem().value);
this.output += start.getItem().value;
if (start.getRightChild() !== null) {
this.inOrderTraversePrint(start.getRightChild());
}; // end if
if (!start.isLeaf()) {
// console.log(")");
this.output += ")";
}
} // end inOrderTraversePrint
inOrderTraverseHtml(start = this.rootPtr) {
if (!start.isLeaf()) {
this.html += "<ul>"
} else {
this.html += "<li>"
} // end if
if (start.getLeftChild() !== null) {
this.inOrderTraverseHtml(start.getLeftChild());
}; // end if
this.html += `<a href="#">${start.getItem().value}</a>`;
if (start.getRightChild() !== null) {
this.inOrderTraverseHtml(start.getRightChild());
}; // end if
if (!start.isLeaf()) {
this.html += "</ul>"
} else {
this.html += "</li>"
} // end if
} // end inOrderTraverseHtml
preOrderTraverse(cb, treePtr = this.rootPtr) {
if (treePtr !== null) {
let Item = treePtr.getItem();
cb(Item, treePtr.id);
this.inOrderTraverse(cb, treePtr.getLeftChild());
this.inOrderTraverse(cb, treePtr.getRightChild());
}
} // end preOrderTraverse
postOrderTraverse(cb, treePtr = this.rootPtr) {
if (treePtr !== null) {
this.inOrderTraverse(cb, treePtr.getLeftChild());
this.inOrderTraverse(cb, treePtr.getRightChild());
let Item = treePtr.getItem();
cb(Item, treePtr.id);
}
} // end postOrderTraverse
addLeft(treePtr = new Node(), newItem) {
let id = this.createId();
while (this.ids.indexOf(id) !== -1) {
id = this.createId();
}
let newNode = new Node(newItem, id);
if (treePtr.getLeftChild() !== null) {
let tempPtr = treePtr.getLeftChild();
newNode.setLeftChild(tempPtr);
treePtr.setLeftChild(newNode);
} else {
treePtr.setLeftChild(newNode);
}
} // end addLeft
addRight(treePtr = new Node(), newItem) {
let id = this.createId();
while (this.ids.indexOf(id) !== -1) {
id = this.createId();
}
let newNode = new Node(newItem, id);
if (treePtr.getRightChild() !== null) {
let tempPtr = treePtr.getRightChild();
newNode.setRightChild(tempPtr);
treePtr.setRightChild(newNode);
} else {
treePtr.setRightChild(newNode);
}
} // end addRight
removeFromIdsHelper(id) {
let index = this.ids.indexOf(id);
this.ids.splice(index, 1);
} // end removeFromIdsHelper
removeRight(treePtr = new Node(), newItem) {
this.removeFromIdsHelper(treePtr.getRightChild().id);
treePtr.setRightChild(null)
// todo: handle existing nodes in children
} // end removeRight
removeLeft(treePtr = new Node(), newItem) {
this.removeFromIdsHelper(treePtr.getLeftChild().id);
treePtr.setLeftChild(null)
// todo: handle existing nodes in children
} // end removeLeft
}
/**
* This is the implementation of the Abstract data type
*/
let tree = new BinaryNodeTree();
function handleCreateClick() {
$("[data-action=start]").off().on("click", function() {
tree.setRoot("Operator", "+");
tree.addLeft(tree.getRoot(), new MathModel("Operator", "-"))
tree.addRight(tree.getRoot(), new MathModel("Number", 20))
tree.addLeft(tree.getRoot().getLeftChild(), new MathModel("Operator", "/"))
tree.addRight(tree.getRoot().getLeftChild(), new MathModel("Number", 60))
tree.addLeft(tree.getRoot().getLeftChild().getLeftChild(), new MathModel("Number", 75))
tree.addRight(tree.getRoot().getLeftChild().getLeftChild(), new MathModel("Number", 60))
console.log("Tree created", "Uncomment line 299 to log it.");
// console.log(tree);
});
}
function handleDrawClick() {
$("[data-action=draw]").off().on("click", function() {
console.log(tree.toString());
$(".output").html(tree.toHTML())
});
}
function invokes() {
handleCreateClick();
handleDrawClick();
}
$(document).ready(() => {
invokes();
})
body {
height: 1000px;
}
<link href="https://stackpath.bootstrapcdn.com/bootstrap/4.1.0/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-9gVQ4dYFwwWSjIDZnLEWnxCjeSWFphJiwGPXr1jddIhOegiu1FwO5qRGvFXOdJZ4" crossorigin="anonymous">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="container">
<div class="row">
<div class="col-xs-12">
<h1>TREE</h1>
<ul>
<li>The Node class starts on line 5</li>
<li>The Math Model class starts on line 45</li>
<li>The Binary Tree class starts on line 69
<ul>
<li>toHTML() starts on line 168</li>
<li>toHTML() calls inOrderTraverseHtml() which is on line 182</li>
<li>This gets called from the implementation on the <span class="btn btn-sm btn-info">Draw</span> event on line 302</li>
</ul>
</li>
<li>The implementation of the Abstract data type starts in JS on line 269</li>
<li>Uncomment line 307 to view the tree</li>
</ul>
<h2>To Start</h2>
<ol>
<li>Click start</li>
<li>Click draw</li>
</ol>
</div>
</div>
<hr/>
<div class="row">
<div class="col-xs-12">
<div class="btn-group">
<div class="btn btn-primary" data-action="start">Start!</div>
<div class="btn btn-info" data-action="draw">Draw!</div>
</div>
</div>
<div class="col-xs-12">
<div class="output"></div>
</div>
</div>
</div>
编辑
我正在尝试创建在 this codeplayer tutorial
中看到的标记编辑 2
我正在包含一个示例，说明我希望输出的外观如何。
<div class="tree">
<ul>
<li>
<a href="#">Parent</a>
<ul>
<li>
<a href="#">Child</a>
<ul>
<li>
<a href="#">Grand Child</a>
</li>
</ul>
</li>
<li>
<a href="#">Child</a>
<ul>
<li><a href="#">Grand Child</a></li>
<li>
<a href="#">Grand Child</a>
<ul>
<li>
<a href="#">Great Grand Child</a>
</li>
<li>
<a href="#">Great Grand Child</a>
</li>
<li>
<a href="#">Great Grand Child</a>
</li>
</ul>
</li>
<li><a href="#">Grand Child</a></li>
</ul>
</li>
</ul>
</li>
</ul>
所以我向 BinaryNodeTree 添加了一个 class 扩展。它在下面并且可以按我需要的方式工作。
class BinaryNodeTreeToHTML extends BinaryNodeTree {
constructor(rootPtr, className = "tree-html") {
super(rootPtr);
this.html = [];
this.rootPtr = rootPtr;
this.className = className;
}
createContainer() {
const _ = this;
return new $("<div />", {
"class": _.className
});
}
createListItem(type, value, id, parentId) {
const _ = this;
return $("<li />", {
id,
"data-parent_id": parentId,
"data-type": type,
"data-value": value,
html: _.createAnchor(type, value)
});
}
createAnchor(type, value) {
return $("<a />", {
href: "#",
"data-type": type,
text: value
});
}
createUnorderedList(parent = "root") {
return $("<ul />", {
"data-parent": parent
})
}
Start(outputClassName) {
const _ = this;
console.log(this.Root);
const $output = $(`.${outputClassName}`).eq(0);
const $container = this.createContainer();
let $main_ul = _.createUnorderedList();
$container.append($main_ul);
$output.append($container);
console.log(_.html);
this.inOrderTraverse((Item, Id, Pointer, Parent) => {
if (Parent !== null) {
let $new_item = _.createListItem(Item.Type, Item.Value, Id, Parent.Id);
$main_ul.append($new_item);
} else {
let $new_item = _.createListItem(Item.Type, Item.Value, Id, "root");
$main_ul.append($new_item);
}
})
for(let obj of $main_ul.find("li")){
let $obj = $(obj);
if($obj.data().parent_id !== "root"){
let $parent = $("#"+$obj.data().parent_id);
if($parent.find("[data-parent="+$parent.attr("id")+"]").length > 0){
let $ul = $parent.find("[data-parent="+$parent.attr("id")+"]")
$ul.append($obj);
}else{
$parent.append(_.createUnorderedList($parent.attr("id")).append($obj))
}
}
}
return $container;
}
};
我一直在思考这个问题。我很高兴你想出了对你有用的东西。我仍然没有尝试通过您的代码工作。对于我有限的注意力来说，实在是太多了。
但潜在的问题让我感兴趣，我有一个从头开始编写的非常不同的解决方案。
更简单的树
我们从更简单的树结构开始。
const node = (val, left, right) => ({val, left, right})
const preorder = (before, after, node) =>
[before(node.val)]
.concat(node.left ? preorder(before, after, node.left) : [])
.concat(node.right ? preorder(before, after, node.right) : [])
.concat(after(node.val))
问题似乎需要 preorder 遍历，而不是 inorder 遍历。如果我们想要 inorder 遍历，这很简单：
const inorder = (fn, node) =>
(node.left ? inorder(fn, node.left) : [])
.concat(fn(node.val))
.concat(node.right ? inorder(fn, node.right) : [])
请注意，这些遍历只是将每个节点上的函数调用结果收集到一个数组中。为了处理您希望 HTML 个节点在我们的预购版本中相互包装这一事实，我们有单独的 before 和 after 函数。我们稍后会用到它。
像这样构建的树可以非常简单：
node(
'+',
18,
node('*', 4, 6)
)
这会生成这样的 object：
{
val: "+",
left: 18,
right: {
val: "*",
left: 4,
right: 6
}
}
或者如果你愿意，你可以这样做
node(
node('+'),
node(18),
node('*', node(4), node(6))
)
看起来更像这样：
{
val: {
val: "+",
left: undefined,
right: undefined
},
left: {
val: 18,
left: undefined,
right: undefined
},
right: {
val: "*",
left: {
val: 4,
left: undefined,
right: undefined
},
right: {
val: 6,
left: undefined,
right: undefined
}
}
}
如果你打算这样做，你可能更喜欢这个稍微复杂一点的 node:
const node = (val, left, right) =>
Object.assign({val}, left ? {left} : {}, right ? {right} : {})
删除那些 undefineds，给你留下类似
{
val: {
val: "+"
},
left: {
val: 18
},
right: {
val: "*",
left: {
val: 4
},
right: {
val: 6
}
}
}
节点类型
对于这个问题，我们要考虑两种不同类型的节点，operators 和 numbers。我们创建了两个简单的函数来包装它们：
const operator = (value) => ({type: 'op', value})
const number = (value) => ({type: 'num', value})
请注意，这些类型和上面的 node/tree 函数比您从 OO 语言移植过来要简单得多。 Javascript 是一种更高级的语言，它在很多方面都比 Java/C++/C#/etc.
更简单示例数据
使用这些节点类型，我们可以像这样创建请求的树：
const myTree = node(
operator('+'),
node(
operator('-'),
node(
operator('/'),
node(number(60)),
node(number(75)),
),
node(number(60))
),
node(number(20))
)
这个问题是以更零碎的方式构建的。我们可以随心所欲地这样做，通过 myTree.left.left.right 等选择器访问节点，并为它们的 left、right 和 val 属性赋值。在任何动态情况下，我们可能都必须这样做。但是如果我们把整个结构放在前面，那就更干净了。
HTML代
我们的 preorder 函数访问每个节点两次，一次在 children（如果有）之前，一次在它们之后。所以我猜它不是真正的 preorder，而是 postorder 的组合。但这适用于我们想要做 before-and-after HTML 片段的 use-case。
const toHtml = (tree) => `<div class='tree'><ul>` + preorder(
node => node.type === 'op'
? `<li><a class="${node.type}" href="#">${node.value}</a><ul>`
: `<li><a class="${node.type}" href="#">${node.value}</a></li>`,
node => node.type === 'op'
? `</ul></li>`
: ``,
tree
).join('') + `</ul></div>`
这是针对我们的问题的，它在提供给 preorder 的前后函数中生成标记，加入结果数组，并将其包装在请求的 <div> 标记中.我们将 CSS 类 添加到标记中，以防有帮助。
用法
把这些放在一起，我们得到
toHtml(myTree)
这将生成类似
的内容<div class='tree'>
<ul>
<li>
<a class="op" href="#">+</a>
<ul>
<li>
<a class="op" href="#">-</a>
<ul>
<li>
<a class="op" href="#">/</a>
<ul>
<li>
<a class="num" href="#">60</a>
</li>
<li>
<a class="num" href="#">75</a>
</li>
</ul>
</li>
<li>
<a class="num" href="#">60</a>
</li>
</ul>
</li>
<li>
<a class="num" href="#">20</a>
</li>
</ul>
</li>
</ul>
</div>
（虽然没有花哨的缩进。）
演示
我们可以在这段代码中看到这一切是如何协同工作的：
// Binary Tree Implementation
const node = (val, left, right) => ({val, left, right})
const preorder = (before, after, node) =>
[before(node.val)]
.concat(node.left ? preorder(before, after, node.left) : [])
.concat(node.right ? preorder(before, after, node.right) : [])
.concat(after(node.val))
// Node types
const operator = (value) => ({type: 'op', value})
const number = (value) => ({type: 'num', value})
// HTML Generation
const toHtml = (tree) => `<div class='tree'><ul>` + preorder(
node => node.type === 'op'
? `<li><a class="${node.type}" href="#">${node.value}</a><ul>`
: `<li><a class="${node.type}" href="#">${node.value}</a></li>`,
node => node.type === 'op'
? `</ul></li>`
: ``,
tree
).join('') + `</ul></div>`
// Sample Data
const myTree = node(
operator('+'),
node(
operator('-'),
node(
operator('/'),
node(number(60)),
node(number(75)),
),
node(number(60))
),
node(number(20))
)
// Usage
console.log(toHtml(myTree))
总结
这并没有回答您关于为什么您的代码无法运行的基本问题，但它提供了我认为在 Javascript 中处理树木的更简单的解决方案，并创建了一种构建输出的方法你正在寻找一个。
Javascript 至少和 Object-Oriented 一样是一种函数式语言。这里的技术相当实用，使用简单、纯函数。我相信他们会制作出更简洁的程序。