在二叉搜索树中找到最大深度
|
这是二进制搜索树的代码
#include<stdio.h>
#include<conio.h>
#include\"malloc.h\"
struct node
{
int data;
struct node* left;
struct node* right;
};
int size(struct node* n)
{
if(n==NULL)
return 0;
else
return (size(n->left)+1+size(n->right));
}
int maxdepth(struct node* n)
{
int ldepth,rdepth;
if(n==NULL)
{
return 0;
}
else
{
ldepth=maxdepth(n->left);
rdepth=maxdepth(n->right);
if(ldepth>rdepth)
return (ldepth+1);
else
return (rdepth+1);
}
}
int lookup(struct node* node,int target)
{
if(node==NULL)
return 0;
else if(target==node->data)
return 1;
else if(target<node->data)
return(lookup(node->left,target));
else
return(lookup(node->right,target));
}
struct node* newnode(int data)
{
struct node* newnod=(struct node*)malloc(sizeof(struct node));
newnod->data=data;
newnod->left=NULL;
newnod->right=NULL;
return newnod;
}
struct node* insert(struct node* root,int target)
{
if(root==NULL)
return(newnode(target));
else if(target<=root->data)
root->left=insert(root->left,target);
else
root->right=insert(root->right,target);
return root;
}
void main()
{
int result,s,max;
struct node* newnode=NULL;
clrscr();
newnode=insert(newnode,2);
newnode=insert(newnode,3);
newnode=insert(newnode,4);
max=maxdepth(newnode);
printf(\"maxdepth %d\\n\",max);
s=size(newnode);
result=lookup(newnode,3);
printf(\"size %d\\n\",s);
printf(\"%d\",result);
getch();
}
当我运行该程序时。我得到maxdepth
有3。
如果我将maxdepth
函数更改为
int maxdepth(struct node* n)
{
int ldepth,rdepth;
if(n==NULL)
{
return 0;
}
else
{
ldepth=maxdepth(n->left);
rdepth=maxdepth(n->right);
if(ldepth>rdepth)
return (ldepth);
else
return (rdepth);
}
}
我将maxdepth
值设为0。这是什么问题?我不明白吗?
没有找到相关结果
已邀请:
2 个回复
味芯憨
。
没有the5ѭ
总是返回
。因为
和
将始终是
。 具有3个节点的树的示例:
现在调用
,它将执行:
,然后
将进行:
,因此
将返回结果
。类似的ѭ20return将返回
。然后,您将执行以下操作:
但是
和
都是
,因此将返回
,即
。最后,
将返回0。 这就是为什么需要5英镑的原因。
剿畦缄饥小
在这棵树中,我们处于完美平衡状态,因此我们不必担心每个节点上哪个子树更高(它们的高度相同)。因此,我们将只使用左侧分支来计算高度。 那棵树的高度是多少?这是ѭ31的高度。
的高度是多少?它是高度
的一加。 反过来,ѭ33的高度为1加上ѭ35的高度,and35的高度为1加上ѭ35的左分支的高度(为零)。 因此总高度为
。 因此,这种(简化)情况下的算法为:
这就是为什么递归高度函数必须在每个级别添加一个。如果改为加0(这是第二个代码段的作用),则从获得
切换为获得
。 如果您修改上述算法以考虑子树的不同大小,则基本上可以得到第一个代码段,该代码段运行良好: