1、兩棵空二叉樹或僅有根結點的二叉樹相似;對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
//結束similar
2、 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上,層次遍歷序列中的每個結點都是「區域性根」。確定根後,到二叉樹的中序序列中,查到該結點,該結點將二叉樹分為「左根右」三部分。
若左、右子樹均有,則層次序列根結點的後面應是左右子樹的根;若中序序列中只有左子樹或只有右子樹,則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣,定義乙個全域性變數指標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; i if (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);
}//演算法結束
3、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a,取出a[i](0<=ilinkedlist creat(elemtype a,int n)
//由含n個資料的陣列a生成迴圈鍊錶,要求鍊錶有序並且無值重複結點
//查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);
}演算法結束
2023年陝西省資料總結要領
1 有乙個帶頭結點的單鏈表,每個結點包括兩個域,乙個是整型域info,另乙個是指向下乙個結點的指標域next。假設單鏈表已建立,設計演算法刪除單鏈表中所有重複出現的結點,使得info域相等的結點只保留乙個。include typedef char datatype typedef struct no...
2023年陝西省資料要領大綱
1 題目中要求矩陣兩行元素的平均值按遞增順序排序,由於每行元素個數相等,按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和,放入一維陣列中,然後選擇一種排序方法,對該陣列進行排序,注意在排序時若有元素移動,則與之相應的行中各元素也必須做相應變動。void translation f...
2023年陝西省資料總結加強
1 設t是一棵滿二叉樹,編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。2 兩棵空二叉樹或僅有根結點的二叉樹相似 對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。int similar bitree p,q 判斷二叉樹p和q是否相似 結束similar 3 因為後序遍歷棧中保留當前結點...