二叉樹排序樹最近公共祖先

數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系姓 名黃玉標(biāo)學(xué) 號1104031002班級網(wǎng)絡(luò)工程一班指導(dǎo)老師 王竹婷實(shí)驗(yàn)題目設(shè)計(jì)算法實(shí)現(xiàn)在二叉排序樹上查找任意兩個(gè)不同結(jié)點(diǎn)的最近公共祖先。問題分析本題可采取對二叉排序樹地址隊(duì)列操作來實(shí)現(xiàn)。要完成該任務(wù)，須完成以下子任務(wù)：建立二叉樹進(jìn)行添加數(shù)據(jù)操作；輸出添加的數(shù)據(jù)以確認(rèn)算法正確；遍歷二叉樹結(jié)點(diǎn)找出對應(yīng)的位置；找出其公共祖先設(shè)計(jì)主函數(shù)，完成以上功能。概要設(shè)計(jì)為完成任務(wù)，程序包含了4個(gè)函數(shù)：主函數(shù)main()；建表初始化函數(shù)Create()；輸出函數(shù)Show()；結(jié)點(diǎn)位置獲取函數(shù)CountLeap(Bitree*T)；最近祖先獲取函數(shù)。詳細(xì)設(shè)計(jì)#include<stdlib.h>#include<stdio.h>#defineMAX10typedefstructnode(chardata;structnode*lchild,*rchild;}Bitree;//聲明Bitree結(jié)點(diǎn)類型Bitree*Q[MAX];Bitree*Create(){〃創(chuàng)建二叉樹并添加數(shù)據(jù)charch;intfront,rear;Bitree*T,*S;T=NULL;front=1;rear=0;printf("enterchar '@'empty,'#'end\n");scanf("%c”,&ch);while(ch!='#'){S=NULL;if(ch!='@'){S=(Bitree*)malloc(sizeof(Bitree));S->data=ch;S->lchild=NULL;S->rchild=NULL;}rear++;Q[rear]=S;if(rear==1)T=S;else(if(S!=NULL&&Q[front]!=NULL)if(rear%2==0)Q[front]->lchild=S;elseQ[front]->rchild=S;if(rear%2==1)front++;}scanf("%c",&ch);}returnT;}voidShow(Bitree*T)(//先序顯示二叉樹內(nèi)容if(T==NULL)return;printf("%c”,T->data);Show(T->lchild);Show(T->rchild);}intGetNodePos(charch)(〃獲取相應(yīng)結(jié)點(diǎn)在隊(duì)列中的位置inti;for(i=1;Q[i]!=NULL;i++){if(ch==Q[i]->data)returni;}return-1;}voidSearchNstOrig(inta,intb){〃獲取最近祖先if(a==-1||b==-1){printf("error\n");return;}if(a==111b==1)gotoflagl;flag：if(a==b){flagl:printf("%c\n",Q[a]->data);return;}if(a>b){a=a/2;gotoflag;}if(a<b){b=b/2;gotoflag;}}voidmain(){Bitree*tree;tree=Create();Show(tree);printf("\n");printf("%d\n”,GetNodePos('a'));SearchNstOrig(GetNodePos('c'),GetNodePos('b'));調(diào)試分析本次詳細(xì)代碼為正確的，但是調(diào)試過程中確實(shí)存在問題，在這里說一下，問題顯示為E:\C語言編程\實(shí)驗(yàn)'樹的應(yīng)用實(shí)驗(yàn)\算法設(shè)計(jì)2\Text1.cpp(61):errorC2819:type'node'doesnothaveanoverloadedmember'operator->'E:\C語言編程\實(shí)驗(yàn)'樹的應(yīng)用實(shí)驗(yàn)\算法設(shè)計(jì)2\Text1.cpp(5):seedeclarationof'node'E:\C語言編程'實(shí)驗(yàn)'樹的應(yīng)用實(shí)驗(yàn)\算法設(shè)計(jì)2\Text1.cpp(61):errorC2227:leftof'->dat