1、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上,層次遍歷序列中的每個結點都是「區域性根」。確定根後,到二叉樹的中序序列中,查到該結點,該結點將二叉樹分為「左根右」三部分。
若左、右子樹均有,則層次序列根結點的後面應是左右子樹的根;若中序序列中只有左子樹或只有右子樹,則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣,定義乙個全域性變數指標r,指向層次序列待處理元素。演算法中先處理根結點,將根結點和左右子女的資訊入佇列。
然後,在佇列不空的條件下,迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下:
typedef struct
qnode;
bitree creat(datatype in,level,int n)
//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數
qnode s,qq是元素為qnode型別的佇列,容量足夠大
init(q); int r=0; //r是層次序列指標,指向當前待處理的結點
bitree p=(bitree)malloc(sizeof(binode生成根結點
p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料
for (i=0; iif (in[i]==level[0]) break;
if (i==0) //根結點無左子樹,遍歷序列的1—n-1是右子樹
else if (i==n-1) //根結點無右子樹,遍歷序列的1—n-1是左子樹
else //根結點有左子樹和右子樹
while (!empty(q)) //當佇列不空,進行迴圈,構造二叉樹的左右子樹
else if (i==
else
}//結束while (!empty(q))
return(p);
}//演算法結束
2、(1)p->rchild (2)p->lchild (3)p->lchild (4)addq(q,p->lchild) (5)addq(q,p->rchild)
25. (1)t->rchild!=null (2)t->rchild!=null (3)n0++ (4)count(t->lchild) (5)count(t->rchild)
26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild
27. (1)*ppos // 根結點(2)rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1
3、陣列a和b的元素分別有序,欲將兩陣列合併到c陣列,使c仍有序,應將a和b拷貝到
c,只要注意a和b陣列指標的使用,以及正確處理一陣列讀完資料後將另一陣列餘下元素復
製到c中即可。
void union(int a,b,c,m,n)
//整型陣列a和b各有m和n個元素,前者遞增有序,後者遞減有序,本演算法將a和b歸併
為遞增有序的陣列c。
演算法結束
4、要求二叉樹按二叉鍊錶形式儲存。15分
(1)寫乙個建立二叉樹的演算法。(2)寫乙個判別給定的二叉樹是否是完全二叉樹的演算法。
bitree creat建立二叉樹的二叉鍊錶形式的儲存結構
else error(「輸入錯誤」);
return(bt);
}//結束 bitree
int judgecomplete(bitree bt) //判斷二叉樹是否是完全二叉樹,如是,返回1,否則,返回0
//while
return 1; } //judgecomplete
4、假設以鄰接矩陣作為圖的儲存結構,編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路,若存在,則以頂點序列的方式輸出該迴路(找到一條即可)。(注:圖中不存在頂點到自己的弧)
有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷,將頂點分成三類:未訪問;已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。
下面用0,1,2表示這三種狀態。前面已提到,若dfs(v)結束前出現頂點u到v的回邊,則圖中必有包含頂點v和u的迴路。對應程式中v的狀態為1,而u是正訪問的頂點,若我們找出u的下一鄰接點的狀態為1,就可以輸出迴路了。
void print(int v,int start ) //輸出從頂點start開始的迴路。
//if
void dfs(int v)
//if
else
visited[v]=2;
}//dfs
void find_cycle() //判斷是否有迴路,有則輸出鄰接矩陣。visited陣列為全域性變數。
//find_cycle
2023年江西省資料總結加強
1 設t是一棵滿二叉樹,編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。2 設一棵二叉樹的結點結構為 llink,info,rlink root為指向該二叉樹根結點的指標,p 和q分別為指向該二叉樹中任意兩個結點的指標,試編寫一演算法ancestor root,p,q,r 該演算法找到p和...
2023年江西省資料總結要領
1 本題應使用深度優先遍歷,從主調函式進入dfs v 時,開始記數,若退出dfs 前,已訪問完有向圖的全部頂點 設為n個 則有向圖有根,v為根結點。將n個頂點從1到n編號,各呼叫一次dfs 過程,就可以求出全部的根結點。題中有向圖的鄰接表儲存結構 記頂點個數的變數 以及訪問標記陣列等均設計為全域性變...
2023年江西省資料總結入門
1 矩陣中元素按行和按列都已排序,要求查詢時間複雜度為o m n 因此不能採用常規的二層迴圈的查詢。可以先從右上角 i a,j d 元素與x比較,只有三種情況 一是a i,j x,這情況下向j 小的方向繼續查詢 二是a i,j void search datatype a int a,b,c,d,d...