C語言判定一棵二叉樹是否為二叉搜索樹的方法分析

更新時間：2018年08月29日 10:28:01 作者：xiaofei0859

這篇文章主要介紹了C語言判定一棵二叉樹是否為二叉搜索樹的方法,結(jié)合實例形式綜合對比分析了C語言針對二叉搜索樹判定的原理、算法、效率及相關(guān)實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了C語言判定一棵二叉樹是否為二叉搜索樹的方法。分享給大家供大家參考，具體如下：

問題

給定一棵二叉樹，判定該二叉樹是否是二叉搜索樹（Binary Search Tree）？

解法1:暴力搜索

首先說明一下二叉樹和二叉搜索樹的區(qū)別。二叉樹指這樣的樹結(jié)構(gòu)，它的每個結(jié)點(diǎn)的孩子數(shù)目最多為2個；二叉搜索樹是一種二叉樹，但是它有附加的一些約束條件，這些約束條件必須對每個結(jié)點(diǎn)都成立：

結(jié)點(diǎn)node的左子樹所有結(jié)點(diǎn)的值都小于node的值。
結(jié)點(diǎn)node的右子樹所有結(jié)點(diǎn)的值都大于node的值。
結(jié)點(diǎn)node的左右子樹同樣都必須是二叉搜索樹。

該問題在面試中也許經(jīng)常問到，考察的是對二叉搜索樹定義的理解。初看這個問題，也許會想這樣來實現(xiàn)：

假定當(dāng)前結(jié)點(diǎn)值為k。對于二叉樹中每個結(jié)點(diǎn)，判斷其左孩子的值是否小于k，其右孩子的值是否大于k。如果所有結(jié)點(diǎn)都滿足該條件，則該二叉樹是一棵二叉搜索樹。

很不幸的是，這個算法是錯誤的?？紤]下面的二叉樹，它符合上面算法的條件，但是它不是一棵二叉搜索樹。

     10
   / \
5   15     -------- binary tree (1)
     / \
    6    20

那么，根據(jù)二叉搜索樹的定義，可以想到一種暴力搜索的方法來判定二叉樹是否為二叉搜索樹。

假定當(dāng)前結(jié)點(diǎn)值為k。則對于二叉樹中每個結(jié)點(diǎn)，其左子樹所有結(jié)點(diǎn)的值必須都小于k，其右子樹所有結(jié)點(diǎn)的值都必須大于k。

暴力搜索算法代碼如下，雖然效率不高，但是它確實能夠完成工作。該解法最壞情況復(fù)雜度為O(n^2)，n為結(jié)點(diǎn)數(shù)目。（當(dāng)所有結(jié)點(diǎn)都在一邊的時候出現(xiàn)最壞情況）

/*判斷左子樹的結(jié)點(diǎn)值是否都小于val*/
bool isSubTreeLessThan(BinaryTree *p, int val)
{
 if (!p) return true;
 return (p->data < val &&
     isSubTreeLessThan(p->left, val) &&
     isSubTreeLessThan(p->right, val));
}
/*判斷右子樹的結(jié)點(diǎn)值是否都大于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);
}

一個類似的解法是：對于結(jié)點(diǎn)node，判斷其左子樹最大值是否大于node的值，如果是，則該二叉樹不是二叉搜索樹。如果不是，則接著判斷右子樹最小值是否小于或等于node的值，如果是，則不是二叉搜索樹。如果不是則接著遞歸判斷左右子樹是否是二叉搜索樹。（代碼中的maxValue和minValue函數(shù)功能分別是返回二叉樹中的最大值和最小值，這里假定二叉樹為二叉搜索樹，實際返回的不一定是最大值和最小值）

int isBST(struct node* node)
{
 if (node==NULL) return(true);
 //如果左子樹最大值>=當(dāng)前node的值，則返回false
 if (node->left!=NULL && maxValue(node->left) >= node->data)
  return(false);
 // 如果右子樹最小值<=當(dāng)前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);
}

解法2：更好的解法

以前面提到的binary tree(1)為例，當(dāng)我們從結(jié)點(diǎn)10遍歷到右結(jié)點(diǎn)15時，我們知道右子樹結(jié)點(diǎn)值肯定都在10和+INFINITY（無窮大）之間。當(dāng)我們遍歷到結(jié)點(diǎn)15的左孩子結(jié)點(diǎn)6時，我們知道結(jié)點(diǎn)15的左子樹結(jié)點(diǎn)值都必須在10到15之間。顯然，結(jié)點(diǎn)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)
   );
}

由于該算法只需要訪問每個結(jié)點(diǎn)1次，因此時間復(fù)雜度為O(n)，比解法1效率高很多。

解法3：中序遍歷算法

因為一棵二叉搜索樹的中序遍歷后其結(jié)點(diǎn)值是從小到大排好序的，所以依此給出下面的解法。該解法時間復(fù)雜度也是O(n)。

bool isBSTInOrder(BinaryTree *root)
{
 int prev = INT_MIN;
 return isBSTInOrderHelper(root, prev);
}
/*該函數(shù)判斷二叉樹p是否是一棵二叉搜索樹，且其結(jié)點(diǎn)值都大于prev*/
bool isBSTInOrderHelper(BinaryTree *p, int& prev)
{
 if (!p) return true;
 if (isBSTInOrderHelper(p->left, prev)) { // 如果左子樹是二叉搜索樹，且結(jié)點(diǎn)值都大于prev
  if (p->data > prev) { //判斷當(dāng)前結(jié)點(diǎn)值是否大于prev，因為此時prev已經(jīng)設(shè)置為已經(jīng)中序遍歷過的結(jié)點(diǎn)的最大值。
   prev = p->data;
   return isBSTInOrderHelper(p->right, prev); //若結(jié)點(diǎn)值大于prev，則設(shè)置prev為當(dāng)前結(jié)點(diǎn)值，并判斷右子樹是否二叉搜索樹且結(jié)點(diǎn)值都大于prev。
  } else {
   return false;
  }
 }
 else {
  return false;
 }
}

希望本文所述對大家C語言程序設(shè)計有所幫助。

您可能感興趣的文章: