请编写一个判别给定二叉树是否为二叉排序树的算法。

北顾岛城

递归形式

//将中序遍历数据存在一个数组中

int data[SIZE]判断 二叉排序树,i = 0;

void inOrder(Node *p){

if(p != null){

inOrder(p -> lchild);

data[i++] = p -> data;

inOrder(p -> rchild);

}

int checkBST(BTree *t){

return checkBST(t -> root);

int checkBST(Node *p){

inOrder(p);

for(int k = 0; k < i - 1; k++){

if(data[k] >= data[k + 1])

return 0;

}

return 1;

非递归形式

//将中序遍历数据存在一个数组中

int data[SIZE]判断 二叉排序树, i = 0;

void inOrder(Node *p){

Node *st[SIZE];

int top = -1;

while(top != -1 || p != null){

while(p != null){

st[++top] = p;

p = p -> lchild;

}

if(top != -1){

p = st[top--];

data[i++] = p -> data;

p = p -> rchild;

}

}

int checkBST(BTree *t){

return checkBST(t -> root);

int checkBST(Node *p){

inOrder(p);

for(int k = 0; k < i - 1; k++){

if(data[k] >= data[k + 1])

return 0;

}

return 1;

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-143024-1.html