函数式程序设计二叉树作业
函数式程序设计二叉树作业
提问于 2019-03-19 04:00:00
因此，我不得不为二叉树编写一个插入函数，使其成为二进制搜索树，但我遇到了一些麻烦。一切都是函数，所以我理解没有状态的概念。因此，在插入时，我需要递归地创建树。我很难接受这个想法。
treenode -> procedure(val, left, right) procedure(some) if some then -(some, 1) then right else left else val这允许我创建节点并访问值，如左子树和右子树(0表示空树)：
.treenode(4, 0, 0)要创建更复杂的树，我可以这样做：
.treenode(4, .treenode(3, 0, 0), .treenode(6, .treenode(2, 0, 0), 0))我甚至插进了一棵空树：
insert -> procedure(root, value) if empty(root) then .treenode(value, 0, 0) else insert_recursive(root, .treenode(value, 0, 0)这就是我想不出如何插入这样的树的地方。在这种语言中不存在状态的概念，所以我需要以某种方式递归地将带有值的新节点追加到当前树上。如果有人能给我个提示，我会很感激的。我该怎么称呼这是：
tree = empty
tree = insert(tree, 4)
tree = insert(tree, 6)
....
and so onStack Overflow用户
发布于 2019-03-19 04:22:54
我以前从未见过这种语法，所以请原谅我的语法错误。希望代码能说明我们需要做什么-
- 如果树为空，则没有可与之比较的值，请使用该值创建一个单例节点。这是你已经完成的部分。
- 否则，树不是空的，因此我们有一个值可以比较。如果要插入的值小于根的值，则创建一个由根值组成的新节点，将该值插入根的左分支，并将根的右分支保持不变
- 如果值大于根值，则执行上述操作，但将新值插入根的右侧分支，而不是左侧
- 该值既不小于--也不大于根的值，因此它等于根的值，没有什么可插入的。在这种情况下，返回未经修改的根。
项目要点对应于下面编号的注释-
insert -> procedure(root, value)
if empty(root) then #1
.treenode(value, 0, 0)
else if value < root.value #2
.treenode (root.value, insert(root.left, value), root.right)
else if value > root.value #3
.treenode (root.value, root.left, insert(root.right, value))
else #4
rootStackOverflow允许我们在应答帖子中直接运行JavaScript片段。这里有一个功能片段，可以让你看到这个概念的行动-
const empty =
{}
const treenode = (value, left = empty, right = empty) =>
({ value, left, right })
const insert = (t, value) =>
t === empty
? treenode (value, empty, empty)
: value < t.value
? treenode (t.value, insert (t.left, value), t.right)
: value > t.value
? treenode (t.value, t.left, insert (t.right, value))
: t
const print = (t, pre = '', child = '') =>
t === empty
? pre + '∅\n'
: print
( t.right
, child + '┌── '
, child + '. '
)
+ pre + String (t.value) + '\n'
+ print
( t.left
, child + '└── '
, child + '. '
)
let tree = empty
tree = insert (tree, 4)
tree = insert (tree, 6)
tree = insert (tree, 9)
tree = insert (tree, 3)
tree = insert (tree, 5)
tree = insert (tree, 1)
console.log (print (tree))
该程序打印构造的tree。∅符号表示空-
. . . ┌── ∅
. . ┌── 11
. . . └── ∅
. ┌── 9
. . └── ∅
┌── 6
. . ┌── ∅
. └── 5
. . └── ∅
4
. ┌── ∅
└── 3
. . ┌── ∅
. └── 1
. . └── ∅页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55233449
复制相关文章
相似问题
腾讯云开发者
