题
你们能帮我用算法来做这些事情吗?我实现了前序、中序和后序,并且提示我使用这些顺序之一遍历树。我使用 dotty 来标记(或“访问”)节点。
深度是从根到底部叶子的边数,所以每次移动时,深度都会加1?类似的事情?
不知道后代的算法。他们询问特定节点自身下的节点数量。
顺便说一句,这些都是普通的树。
解决方案
depth(tree) = 1+ max(depth(tree.left), depth(tree.right));
descendants(tree) = descendants(tree.left) + descendants(tree.right);
对于任何一个,返回0的零指针都将结束递归。
其他提示
这是家庭作业的问题吗?我的回答假设这是为了家庭作业。
树是一种递归数据结构,因此对其进行操作的算法通常是递归的。递归算法需要一个基本情况和一个归纳情况。对于树来说,基本情况是您访问叶节点时所做的事情(即没有子节点的节点)。归纳情况是您访问内部节点时所做的事情(即至少有一个子节点的节点)。
用于计算深度(或树的“高度”):
- 基本情况:没有子节点的节点的深度是多少?
- 电感案例:假设您拥有所有子节点的深度(可能不同),那么您正在访问的当前节点的深度是多少?
用于计算后代计数:
- 基本情况:没有子节点的节点有多少个后代?
- 电感案例:鉴于您知道所有子节点的后代计数,那么您正在访问的当前节点的后代计数是多少?
我鼓励您提出澄清问题。
不隶属于 StackOverflow