我正在尝试创建一个二叉树。我唯一得到的是树中节点的数量。我首先想到的是使用索引(BFS 顺序)来跟踪总节点数,然后使用递归定义。这是我执行此操作的伪代码。
N = 10 //binary tree total node count
i = 0 //global integer
function()
if i > N
return True
create node i
i = i + 1
function(i) //left
i = i + 1
function(i) //right
我必须在这个定义中使用一个全局变量,这让我觉得我可能违反了递归规则。有没有更好的方法来做我所做的事情,如果是这样,是否可以改进?
注意:我问的是理论方法,不是代码。
编辑:我刚刚意识到这个方法失败了。我愿意接受建议。
说明:这棵树的要求是不向深度添加元素,如果之前的深度没有填充节点(所有节点都有2个 child ),请原谅我没有提到这一点之前,至于我在评论中提到的堆栈,与问题无关,只是迭代遍历树的常规方式。
最佳答案
如果递归定义,树由三个元素组成:
- 一个根节点
- 左子树,它本身就是一棵树
- 右子树,它本身就是一棵树
所有这些都可以是NULL
。
现在我们可以按以下方式将范围 [a, b]
中的数字分布到一棵树中:
- 根包含
(a + b)/2
- 左子树由范围
[a, (a + b)/2 - 1]
递归构建 - 右子树由范围
[(a + b)/2 + 1, b]
递归构建
起点高于终点的范围可能被认为是空的,并导致节点为 NULL
。这种分布确保左右子树的大小最多相差 1,并且在另一层被填充之前,每一层都被完全填满。
例如:
N = 6
[0, 5]
[0, 1] 2 [3, 5]
[0] 1 [] [3] 4 [5]
[] 0 [] [] 3 [] [] 5 []
此外,该算法还构建了 BST(实际上这基本上是二分搜索的“逆向”)。现在是算法本身:
function(a, b):
if b < a: return NULL
n = create node (a + b) / 2
n.left = function(a, (a + b) / 2 - 1)
n.right = function((a + b) / 2 + 1, b)
return n
树可以通过调用生成:
function(1, N)
或者,任何其他参数 a
和 b
都应该起作用,其中 a + N - 1 = b
成立。这两个参数表示树应该持有的范围(包括两者)。
关于创建固定大小的二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41029691/