二叉搜索树的结构(30 分) PTA 模拟+字符串处理 二叉搜索树的节点插入和非递归遍历 #include <stdio.h> #include <stdlib.h> #include <cstring> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; typedef int ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode { ElementType Data; Position parent; BinTree Left; BinTree Right; }; void InsertTree(BinTree &T,int k) { if(!T) { T=(BinTree)malloc(sizeof(TNode)); T->Data=k; T->Left=T->Right=T->parent=NULL; //printf(“%d ”,T->Data); } else { //printf(“11111 ”); Position p=T; Position pre=NULL; while(p) { pre=p; if(p->Data<k) p=p->Right; else p=p->Left; } p=(Position)malloc(sizeof(TNode)); p->Data=k; p->Left=p->Right=NULL; p->parent=pre; if(pre->Data>k) pre->Left=p; else if(pre->Data<k) pre->Right=p; else return ; } } Position Search(BinTree T,int k) { Position p=T; while(p) { if(p->Data>k) p=p->Left; else if(p->Data<k) p=p->Right; else return p; } return NULL; } int GetNumber(BinTree T,int k) { int sum=1; Position p=T; while(p) { if(p->Data>k) p=p->Left; else if(p->Data<k) p=p->Right; else return sum; sum++; } return INF; } int main() { BinTree T=NULL; int n; scanf(“%d”,&n); int v; for(int i=0; i<n; i++) { scanf(“%d”,&v); InsertTree(T,v); } int m; scanf(“%d”,&m); getchar(); char s[110]; int v1,v2; for(int i=0; i<m; i++) { scanf(“%d %s”,&v1,s); if(!strcmp(s,”is”)) { scanf(“%s”,s); scanf(“%s”,s); if(!strcmp(s,”root”)) { if(T&&T->Data==v1) printf(“Yes ”); else printf(“No ”); continue; } else if(!strcmp(s,”left”)) { Position p1=Search(T,v1); scanf(“%s”,s); scanf(“%s %d”,s,&v2); Position p2=Search(T,v2); if(p2&&p1&&p2->Left==p1) printf(“Yes ”); else printf(“No ”); } else if(!strcmp(s,”right”)) { Position p1=Search(T,v1); scanf(“%s”,s); scanf(“%s %d”,s,&v2); Position p2=Search(T,v2); if(p2&&p1&&p2->Right==p1) printf(“Yes ”); else printf(“No ”); } else if(!strcmp(s,”parent”)) { Position p1=Search(T,v1); scanf(“%s %d”,s,&v2); Position p2=Search(T,v2); if(p2&&p1&&p2->parent==p1) printf(“Yes ”); else printf(“No ”); } } else if(!strcmp(s,”and”)) { scanf(“%d %s”,&v2,s); scanf(“%s”,s); if(!strcmp(s,”siblings”)) { Position p1=Search(T,v1); Position p2=Search(T,v2); if(p1&&p2&&p1->parent==p2->parent) printf(“Yes ”); else printf(“No ”); } else if(!strcmp(s,”on”)) { scanf(“%s”,s); scanf(“%s”,s); scanf(“%s”,s); int n1=GetNumber(T,v1); //printf(“%d ”,n1); int n2=GetNumber(T,v2); if(n1==n2&&n1!=INF) printf(“Yes ”); else printf(“No ”); } } } return 0; } /* 5 2 4 1 3 0 8 10 is the root 10 and 100 are siblings 10 and 100 are on the same level 10 is the parent of 100 10 is the left child of 100 100 is the right child of 10 10 and 100 are on the same level 100 is the right child of 10 */
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/86827.html