這是我首先想到的算法：

bool Judge(PBinTree pbt) {PBinTreeNode pLeft, pRight;bool bLeft = false, bRight=false, bRootl=false, bRootr=false;if(pbt == NULL)return true;// 判斷根節點pLeft = pbt->left;pRight = pbt->right;if(pLeft && pLeft->data <= pbt->data){bRootl = true;}else{return false;}if(pRight && pRight->data >= pbt->data){bRootr = true;}else{return false;}// 判斷左右子樹bLeft = Judge(pLeft);bRight = Judge(pRight);// 同時滿足條件才叫二叉排序樹return( bLeft && bRight && bRootl && bRootr); }
但是不能處理

? ? ? 400
??200?????600
100?900?500?700

這樣的情況

應該是這樣的算法

typedef struct node{ int data; struct node *left, *right; }NODE; int judge(NODE *p, int leftbound, int rightbound) { if (p==NULL) return 1; if (p-> data < leftbound || p-> data > rightbound) return 0;//不要等號 if (!judge(p-> left,leftbound,p-> data)) return 0; if (!judge(p-> right, p-> data,rightbound)) return 0; return 1; }
?根值為value, ? 則左子樹值都小于根, ? 右子樹值大于根. ? 即左子樹值 ? (-maxint, ? value) ? 范圍內, ? 右子樹值在(value, ? maxint)范圍內.?

調用為 judge(root,-maxint,maxint)

總結

以上是生活随笔為你收集整理的判断某棵二叉树是否二叉排序树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。