算法解析

創(chuàng)新互聯(lián)堅(jiān)實(shí)的技術(shù)研發(fā)基礎(chǔ)贏得了行業(yè)內(nèi)的良好口碑，公司成立十余年來(lái)，為千余家企業(yè)提供過網(wǎng)站建設(shè)、軟件開發(fā)、搜索引擎優(yōu)化技術(shù)、互聯(lián)網(wǎng)大數(shù)據(jù)整合營(yíng)銷服務(wù)，多年的技術(shù)服務(wù)成功經(jīng)驗(yàn)、眾多的客戶使我們能懂得更多，做得更好。"讓您的網(wǎng)站跑起來(lái)"是我們一直追求的目標(biāo)！

根據(jù)二叉排序樹的定義，對(duì)二叉樹進(jìn)行遞歸遍歷，左子樹關(guān)鍵字比根結(jié)點(diǎn)關(guān)鍵字小，右子樹的關(guān)鍵字比根結(jié)點(diǎn)的關(guān)鍵字大，一旦有不滿足條件則可判斷不是二叉排序樹。通過參數(shù) flag 的值來(lái)判斷，flag 為 1 表示是二叉排序樹，為 0 則表示非二叉排序樹，flag 初值為 1。設(shè)定全局變量 pre(初始值為 NULL)來(lái)指向遍歷過程結(jié)點(diǎn)的前驅(qū)。

代碼

void JudgeBST(BiTree T, int &flag)
{//判斷二叉樹是否為二叉排序樹
	if(T != NULL && flag)
	{JudgeBST(T->lchild, flag); //中序遍歷左子樹
		if(pre == NULL) //中序遍歷的第一個(gè)結(jié)點(diǎn)不必判斷
			pre = T;
		else if(pre->data< T->data)
			pre = T; //前驅(qū)指針指向當(dāng)前結(jié)點(diǎn)
		else flag = 0; //不是二叉排序樹
		JudgeBST(T->rchild, flag); //中序遍歷右子樹
	}
}

思路2

對(duì)二叉排序樹來(lái)說，其中序遍歷序列為一個(gè)遞增有序序列，因此，對(duì)
給定的二叉樹進(jìn)行中序遍歷，如果始終能保持前一個(gè)值比后一個(gè)值小，則說明該二叉樹是一棵二叉排序樹，算法如下。

代碼

KeyType predt=-32767; //predt為全局變量，保存當(dāng)前節(jié)點(diǎn)中序前驅(qū)的值，初值為
-∞
int judgeBST(BSTNode *bt)
{int b1, b2;
	if (bt==NULL) //空樹是一棵二叉排序樹
		return 1;
	else
	{b1=judgeBST (bt->lchild); //判斷左子樹
		if(b1==0ll predt>=bt->key)
			return 0;
		predt=bt->key; //保存當(dāng)前節(jié)點(diǎn)的關(guān)鍵字
		b2=judgeBST (bt->rchild); //判斷右子樹
		return b2;
	}
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：C語(yǔ)言：判斷二叉樹是否為二叉排序樹的算法-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)URL：http://weahome.cn/article/dgpscj.html