2023年四川省資料總結基礎

1、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。

int similar(bitree p,q) //判斷二叉樹p和q是否相似

//結束similar

2、根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全域性指標變數pre（初值為null）和全域性變數flag，初值為true。若非二叉排序樹，則置flag為false。

#define true 1

#define false 0

typedef struct node

*btree;

void judgebst（btree t,int flag）

// 判斷二叉樹是否是二叉排序樹，本演算法結束後，在呼叫程式中由flag得出結論。

//不是完全二叉樹

judgebst （t->rlink,flag）；// 中序遍歷右子樹

}//judgebst演算法結束

3、請設計乙個演算法，要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表，表頭指標為head。二叉樹按二叉鍊錶方式儲存，鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時、空複雜度。