本文實例講述了C語言判定一棵二叉樹是否為二叉搜索樹的方法。分享給大家供大家參考，具體如下：
給定一棵二叉樹，判定該二叉樹是否是二叉搜索樹（Binary Search Tree）？
首先說明一下二叉樹和二叉搜索樹的區別。二叉樹指這樣的樹結構，它的每個結點的孩子數目最多為2個；二叉搜索樹是一種二叉樹，但是它有附加的一些約束條件，這些約束條件必須對每個結點都成立：
該問題在面試中也許經常問到，考察的是對二叉搜索樹定義的理解。初看這個問題，也許會想這樣來實現：
假定當前結點值為k。對于二叉樹中每個結點，判斷其左孩子的值是否小于k，其右孩子的值是否大于k。如果所有結點都滿足該條件，則該二叉樹是一棵二叉搜索樹。
很不幸的是，這個算法是錯誤的。考慮下面的二叉樹，它符合上面算法的條件，但是它不是一棵二叉搜索樹。
10
/ /
5 15 -------- binary tree (1)
/ /
6 20
那么，根據二叉搜索樹的定義，可以想到一種暴力搜索的方法來判定二叉樹是否為二叉搜索樹。
假定當前結點值為k。則對于二叉樹中每個結點，其左子樹所有結點的值必須都小于k，其右子樹所有結點的值都必須大于k。
暴力搜索算法代碼如下，雖然效率不高，但是它確實能夠完成工作。該解法最壞情況復雜度為O(n^2)，n為結點數目。（當所有結點都在一邊的時候出現最壞情況）
/*判斷左子樹的結點值是否都小于val*/bool isSubTreeLessThan(BinaryTree *p, int val){ if (!p) return true; return (p->data < val && isSubTreeLessThan(p->left, val) && isSubTreeLessThan(p->right, val));}/*判斷右子樹的結點值是否都大于val*/bool isSubTreeGreaterThan(BinaryTree *p, int val){ if (!p) return true; return (p->data > val && isSubTreeGreaterThan(p->left, val) && isSubTreeGreaterThan(p->right, val));}/*判定二叉樹是否是二叉搜索樹*/bool isBSTBruteForce(BinaryTree *p){ if (!p) return true; return isSubTreeLessThan(p->left, p->data) && isSubTreeGreaterThan(p->right, p->data) && isBSTBruteForce(p->left) && isBSTBruteForce(p->right);}一個類似的解法是：對于結點node，判斷其左子樹最大值是否大于node的值，如果是，則該二叉樹不是二叉搜索樹。如果不是，則接著判斷右子樹最小值是否小于或等于node的值，如果是，則不是二叉搜索樹。如果不是則接著遞歸判斷左右子樹是否是二叉搜索樹。（代碼中的maxValue和minValue函數功能分別是返回二叉樹中的最大值和最小值，這里假定二叉樹為二叉搜索樹，實際返回的不一定是最大值和最小值）
int isBST(struct node* node){ if (node==NULL) return(true); //如果左子樹最大值>=當前node的值，則返回false if (node->left!=NULL && maxValue(node->left) >= node->data) return(false); // 如果右子樹最小值<=當前node的值，返回false if (node->right!=NULL && minValue(node->right) <= node->data) return(false); // 如果左子樹或者右子樹不是BST，返回false if (!isBST(node->left) || !isBST(node->right)) return(false); // 通過所有測試，返回true return(true);}以前面提到的binary tree(1)為例，當我們從結點10遍歷到右結點15時，我們知道右子樹結點值肯定都在10和+INFINITY（無窮大）之間。當我們遍歷到結點15的左孩子結點6時，我們知道結點15的左子樹結點值都必須在10到15之間。顯然，結點6不符合條件，因此它不是一棵二叉搜索樹。該算法代碼如下：
int isBST2(struct node* node){ return(isBSTUtil(node, INT_MIN, INT_MAX));}/*給定的二叉樹是BST則返回true，且它的值 >min 以及 < max.*/int isBSTUtil(struct node* node, int min, int max){ if (node==NULL) return(true); // 如果不滿足min和max約束，返回false if (node->data<=min || node->data>=max) return(false); // 遞歸判斷左右子樹是否滿足min和max約束條件 return isBSTUtil(node->left, min, node->data) && isBSTUtil(node->right, node->data, max) );}由于該算法只需要訪問每個結點1次，因此時間復雜度為O(n)，比解法1效率高很多。
因為一棵二叉搜索樹的中序遍歷后其結點值是從小到大排好序的，所以依此給出下面的解法。該解法時間復雜度也是O(n)。
bool isBSTInOrder(BinaryTree *root){ int prev = INT_MIN; return isBSTInOrderHelper(root, prev);}/*該函數判斷二叉樹p是否是一棵二叉搜索樹，且其結點值都大于prev*/bool isBSTInOrderHelper(BinaryTree *p, int& prev){ if (!p) return true; if (isBSTInOrderHelper(p->left, prev)) { // 如果左子樹是二叉搜索樹，且結點值都大于prev if (p->data > prev) { //判斷當前結點值是否大于prev，因為此時prev已經設置為已經中序遍歷過的結點的最大值。 prev = p->data; return isBSTInOrderHelper(p->right, prev); //若結點值大于prev，則設置prev為當前結點值，并判斷右子樹是否二叉搜索樹且結點值都大于prev。 } else { return false; } } else { return false; }}希望本文所述對大家C語言程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
