二叉树实现单词检查,改进我的check函数#include <iostream> using namespace std; typedef struct BST { string word; struct BST *lchild,*rchild; }*BSTree; void Insert(BSTree &T,string e) { if(!T) { BSTree p=new BST; p->word=e; p->lchild=p->rchild=NULL; T=p; } else { string s=T->word; int i; if(e.compare(s)<0) Insert(T->lchild,e); else Insert(T->rchild,e); } } void create(BSTree &T) { string ch; T=NULL; while(cin>>ch) { if(ch[0]=='#') break; Insert(T,ch); } } void out(BSTree &T) { if(T) { out(T->lchild); out(T->rchild); cout<<T->word<<" "; } } int Search(BSTree &T,string e) { if(!T) return 0; if(e==T->word) return 1; else if(e.compare(T->word)<0) return Search(T->lchild,e); else return Search(T->rchild,e); } void check(BSTree &T,string e) { if(!T) return ; int i,j,count; string s=T->word; if(e.length()<s.length()) { if(e.length()==s.length()-1) { count=0; for(i=0,j=0; s[i]!='\0'; i++,j++) { if(e[j]!=s[i]) { count++; j--; if(count==2) break; } } if(count<2) cout<<s<<" "; } check(T->rchild,e); } else if(e.length()==s.length()) { count=0; for(i=0,j=0; s[i]!='\0'; i++,j++) { if(e[j]!=s[i]) { count++; if(count==2) break; } } if(count<2) cout<<s<<" "; check(T->lchild,e); check(T->rchild,e); } else if(e.length()>s.length()) { if(e.length()==s.length()+1) { count=0;
时间: 2024-02-14 07:21:39 浏览: 26
您的check函数已经实现了对单词的检查,但是可以进行以下改进:
1. 使用递归的方式,对于当前节点,先判断它的左子树和右子树是否需要进行检查,而不是先判断长度大小再进行左右子树的判断,这样可以减少递归次数,提高效率。
2. 当字符串长度相等时,可以先比较两个字符串是否相等,如果相等就不需要再进行后续的比较了,直接递归左右子树即可。
改进后的代码如下:
void check(BSTree &T,string e) {
if(!T)
return;
string s=T->word;
if(Search(T,e))
cout<<s<<" ";
if(e.length()<s.length())
check(T->lchild,e);
else if(e.length()>s.length())
check(T->rchild,e);
else
{
if(e==s)
return;
int count=0,i=0;
while(i<s.length() && count<2)
{
if(s[i]!=e[i])
count++;
i++;
}
if(count<2)
{
check(T->lchild,e);
check(T->rchild,e);
}
}
}
这样改进后,可以提高检查效率,减少不必要的递归次数。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)