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

PTA7-5⼆叉搜索树的结构（30分）PTA 7-5 ⼆叉搜索树的结构 (30 分)⼆叉搜索树或者是⼀棵空树，或者是具有下列性质的⼆叉树： 若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；它的左、右⼦树也分别为⼆叉搜索树。（摘⾃百度百科）给定⼀系列互不相等的整数，将它们顺次插⼊⼀棵初始为空的⼆叉搜索树，然后对结果树的结构进⾏描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插⼊后，得到⼀棵⼆叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同⼀层上”（指⾃顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩⼦”都是正确的；⽽“4是2的左孩⼦”、“1和3是兄弟结点”都是不正确的。在⼆叉树的结构中增加⼀个⽤于指向⽗亲节点的指针域，并在构建树的时候就记录树的层次#include using namespace std;templatestruct TreeNode{ T data; TreeNode *lchild=NULL; TreeNode *rchild=NULL; TreeNode *parent=NULL; int level; TreeNode(T n) { data=n; lchild=NULL; rchild=NULL; parent=NULL; }};templatevoid AddNode(TreeNode *&subroot,const T&elem){ if(subroot==NULL) { subroot=new TreeNode(elem); subroot->level=0; } else { TreeNode *pre=subroot; int c=1; T t=pre->data; while(true) { t=pre->data; if(elemlchild!=NULL) { c++; pre=pre->lchild; } else { pre->lchild=new TreeNode(elem); pre->lchild->parent=pre; pre->lchild->level=c+1; break; } } else { { if(pre->rchild!=NULL) { c++; pre=pre->rchild; } else { pre->rchild=new TreeNode(elem); pre->rchild->parent=pre; pre->rchild->level=c+1; break; } } } }}templateTreeNode *Search(TreeNode *&subroot,T elem){ if(subroot==NULL) { return NULL; } else if(subroot->data==elem) { return subroot; } else { TreeNode *pre=subroot; while(pre!=NULL) { if(pre->datarchild; } else if(pre->data>elem) { pre=pre->lchild; } else { break; } } return pre; }}int main(){ TreeNode *tree=NULL,*p,*q; int n,num; string ss; cin>>n; for(int i=0; i>num; AddNode(tree,num); } cin>>n; getline(cin,ss); for(int i=0; i>t; cin>>t; cin>>ss; if(ss=="is") { cin>>ss; cin>>ss; if(ss=="root") { if(tree!=NULL&&tree->data==t) { cout<<"Yes"<>ss; cin>>t2; p=Search(tree,t2); if(p!=NULL&&p->parent!=NULL&&p->parent->data==t) { cout<<"Yes"<>ss; cin>>ss; cin>>t2; q=Search(tree,t2); if(q!=NULL&&q->lchild!=NULL&&q->lchild->data==t) { cout<<"Yes"<>ss; cin>>ss; cin>>t2; q=Search(tree,t2); if(q!=NULL&&q->rchild!=NULL&&q->rchild->data==t) { cout<<"Yes"<>t2; getline(cin,ss); if(("siblings")!=string::npos) { p=Search(tree,t); q=Search(tree,t2); if(p!=NULL&&q!=NULL&&p->parent==q->parent) { cout<<"Yes"<level==q->level) { cout<<"Yes"<