这是二叉搜索树的代码
#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。问题是什么?我想不通?
最佳答案
您没有计算当前节点,因此需要 +1
。
{
ldepth = maxdepth(n->left);
rdepth = maxdepth(n->right);
if(ldepth > rdepth)
return ldepth + 1;
else
return rdepth + 1;
}
没有 +1
maxdepth
总是会返回 0
。因为 ldepth
和 rdepth
将始终为 0
。
具有 3 个节点的树的示例:
A
/ \
B C
现在你调用 maxdepth(A)
,这将完成:ldepth = maxdepth(B); rdepth = maxdepth(C);
,然后 maxDepth(B)
将执行:ldepth = maxdepth(null); rdepth = maxdepth(null);/* ldepth 和 rdepth 现在为 0 */
,因此 maxDepth(B)
将作为结果返回 0
。类似的maxDepth(C)
会返回0
。然后你会做:
if(ldepth > rdepth)
return ldepth;
else
return rdepth;
但是ldepth
和rdepth
都是0
,所以rdepth
会返回0
。最后 maxdepth(A)
将返回 0 作为结果。
这就是为什么需要 +1
。
关于c - 在二叉搜索树中查找最大深度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6343668/