gpt4 book ai didi

c - 如何比较二叉树中的根路径和叶路径

转载 作者:行者123 更新时间:2023-11-30 17:57:58 25 4
gpt4 key购买 nike

我正在尝试搜索给定红黑树内的所有根到叶路径。特别是,我想编写一个测试,在给定 rbt 的情况下,将断言每条路径具有相同数量的黑色节点。

我正在尝试使用两个全局变量进行类似的操作:

static int count = 0, path = -1;

int check_paths(tree_node t)
{
if (t == NULL)
{
if (path == -1)
path = count;
else
return (path == count);

return 1;
}

if (t->black == 1) ++count;
int x,y;
x = check_paths(t->left);
if (t->black == 1) --count;
y = check_paths(t->right);

return (x&&y);
}

但是,当左分支中的黑色节点右侧有红色节点时,我遇到了麻烦,因为这意味着计数的减少量超过了应有的量。

是否有更好的方法来搜索根到叶路径并计算特定值的频率,然后以某种方式比较计数?或者,是否有一种完全不同的方法来测试 RBT 的余额(如果给定的话)(即它已经制作,但其正确性不确定)?

最佳答案

考虑如何创建一个采用(子)树的函数,并且(a)如果平衡则返回其黑色高度,或者(b)否则返回负数。

基本情况是一个空(子)树;它只是返回 0。

归纳案例:

  • lh 是左子树递归调用的结果
  • lr 是右子树递归调用的结果

如果 lh == lr 并且它们为正,则返回 lh + 1(如果是黑色)

这是一些未经测试的代码:

int check_paths (tree_node t)
{
if (t == NULL)
{
return 0;
}
int lh = check_paths(t->left);
int rh = check_paths(t->right);

if (lh != rh || lh < 0)
{
return -1;
}
else if (t->black == 1)
{
return (lh + 1);
}
else
{
return (lh)
}
}

关于c - 如何比较二叉树中的根路径和叶路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12546599/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com