2023年6月22日发(作者：)

⼆叉树查找、匹配字符串、快速排序题记：⼀个⾯试题⽬，让我羞耻的⾯试题⽬，40分钟真得没有写出来，C语⾔的指针真是⿇烦到家题⽬⼤意，在⼀个⼆叉树中，找出匹配⼦串的节点，并使⽤快速排序找出第n⼤的节点。排序规则：字串出现次数，字符数，ascii排序。#include #include #include #define SIZE 100struct TreeNode{ char *str; struct TreeNode *left, *right;};struct help{ int num; struct TreeNode *node;};struct help pall[SIZE]={};;int inde =0;int com(struct help *p1,struct help *p2){ if(p1->num < p2->num){ return 1; } if(p1->num == p2->num){ if(strlen(p1->node->str) node->str)) { return 1; } if(strlen(p1->node->str) == strlen(p2->node->str)){ if(strcmp(p1->node->str,p2->node->str) <0){ return 1; } } } return 0;}struct TreeNode * qsort1(struct help *p, int n ,int k){ struct help h = p[0]; int i=0,j=n-1,index=0; if(nstr); }*/ return (p+i)->node; }else if(i >(k-1)){ /*int j=0;for( j=0;jstr); } printf("--------- pre");*/ return qsort1(p,i,k); }else{ /*int j=0;for( j=0;jstr); } printf("--------- back");*/ return qsort1(p+i+1,n-i-1,k-i-1); }}void inorder(struct TreeNode *node, char *substr){ int *next = (int *)malloc(sizeof(int)*(strlen(substr)+1)); if(node == NULL){ return ; } inorder(node->left,substr); int num =findSubNum(node->str,substr,next); if(num>0){struct help h = {num,node}; pall[inde++] = h;} //printf("%s %dn",node->str,num); inorder(node->right,substr);}void getnext(char *str, int next[]){ next[0] = next[1] = 0; int length = strlen(str); int i =0,j=0 ; for( i = 1; i < length ; i++){ while(j>0&&(*(str+i)) != (*(str+j))) j = next[j]; if((*(str+i)) == (*(str+j))) j++; next[i+1] = j; }}int findSubNum(char *str, char *substr,int next[]){ getnext(substr,next); int length = strlen(substr); int i=0,j=0,num=0; for(i = 0; i< strlen(str); i++) { while(j>0&&((*(str+i))!=(*(substr+j)))) j=next[j]; if((*(str+i))==(*(substr+j)) ) j++; if(j == length){ num++; j = next[j]; } } return num;}struct TreeNode *findNode(struct TreeNode *node, char *substr,int n){ inorder(node,substr); /*printf("find node num %dn",inde); int i=0; for( i=0;istr); }*/ qsort1(pall,inde,n);}int main(){ struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1); struct TreeNode *left = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1); struct TreeNode *right = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1); struct TreeNode *leftright = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1); root->left=left; root->right =right; left->left=NULL; left->right=NULL; right->left=NULL; right->right=NULL; left->right = leftright; left->left = NULL; leftright->right =NULL; leftright->left =NULL; leftright->str="abedf"; root->str="abced"; left->str="cbcab"; right->str="babefbaad"; char *substr = "ab"; /*struct help p1 = {2,root}; struct help p2 = {2,left}; struct help p3 = {3,right}; //printf("%d",com(&p1,&p2)); p[0]=p1;p[1]=p2;p[2]=p3;*/ printf("%s",findNode(root,substr,4)->str); //printf("%s",); return 0; //inorder(root,substr);}