思路：若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
它的左、右子樹也分別為二叉排序樹。

遞歸遍歷就可以了，反正就是左孩子的key比根節(jié)點(diǎn)的key小，右孩子的key比根節(jié)點(diǎn)的key大，一旦有不滿足條件的就判定不是。

完整的代碼如下：

#include "stdio.h" #include "stdlib.h" typedef struct node {int data;struct node *lchild,*rchild; }Bitree; Bitree *B[100]; Bitree *CreateBiTree() {int num,i,n;Bitree *t,*s;t=NULL;printf("建立二叉樹（1表示為虛結(jié)點(diǎn)，0表示輸入結(jié)束）：/n");num=0;scanf("%d",&n);while(n!=0){s=(Bitree *)malloc(sizeof(Bitree));s->data=n;s->lchild=s->rchild=NULL;num++;if(!t)t=s;B[num]=s;scanf("%d",&n);}for(i=1;i<=num;i++){if(B[i]->data!=1){if(2*i<=num && B[2*i]->data!=1)B[i]->lchild=B[2*i];if(2*i+1<=num && B[2*i+1]->data!=1)B[i]->rchild=B[2*i+1];}}return t; } int IsSearchTree(const Bitree *t) //遞歸遍歷二叉樹是否為二叉排序樹 {if(!t) //空二叉樹情況return 1;else if(!(t->lchild) && !(t->rchild)) //左右子樹都無情況return 1;else if((t->lchild) && !(t->rchild)) //只有左子樹情況{if(t->lchild->data>t->data)return 0;elsereturn IsSearchTree(t->lchild);}else if((t->rchild) && !(t->lchild)) //只有右子樹情況{if(t->rchild->data<t->data)return 0;elsereturn IsSearchTree(t->rchild);}else //左右子樹全有情況{ if((t->lchild->data>t->data) || (t->rchild->data<t->data))return 0;elsereturn ( IsSearchTree(t->lchild) && IsSearchTree(t->rchild) );} } int main(void) {int flag=0;Bitree *tree;tree=CreateBiTree();flag=IsSearchTree(tree);if(flag)printf("這棵樹是二叉排序樹！/n");elseprintf("這棵樹不是二叉排序樹！/n");system("pause");return 0; }

?

?

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。