判断二叉树是否为二叉搜索树

概要

这题利用二叉搜索树的特性：左子树的所有的关键字小于根节点的关键字，右子树的所有关键字都大于根结点 的关键字。二叉搜索树的中序遍历一定是个有序序列。根据这一特性可以利用二叉树的非递归中序遍历来解答这个问题。

二叉树数据结构

typedef struct node{
    ElemType data;  //数据域
    struct node* lchild;
    struct node* rchild;
}BinaryTree;            

复制

递归算法思路

1）设置全局比较变量last为二叉树数据域对应数据类型的最小值，标志变量flag为真。

2）若树有左子树且标志位flag为真，递归判断左子树是否为二叉排序树。

3）若根节点的数据域小于last，那么flag置为false。

4）把last赋值为当前根节点的数据域。

5）若存在右子树且flag为真，递归判断右子树是否为二叉排序树。

6）返回flag。

代码

int last = -32768;
bool flag = true;
bool JudgeBST(BinaryTree* root)
{
    if(!root->lchild && flag){
        JudgeBST(root->lchild);
    }
    if(root->data < last){
        flag = false;
    }
    last = root->data;
    if(root->rchild && flag){
        JudgeBST(root->rchild);
    }
    return flag;
}           

复制

非递归算法思路

1）初始化堆栈为空，设置data为当前根节点的键值，设置cur指向根节点，标志位flag为true。

2）若cur->lchild非空，那么如果cur->lchild的键值小于data那么cur入栈，cur = cur->lchild，data = cur->data。否则flag = false并结束循环。

3）若cur->lchild为空，那么cur = cur->rchild，此时cur非空，那么若cur->data大于data那么data = cur->data。否则flag = false并结束循环。若cur为空且堆栈非空，那么堆栈一直出栈，并把每出栈的指针的右孩子赋值给cur，并且之后data = cur->datal。

4）当cur为空或者堆栈不空时一直循环上述操作2）与3）。

代码

bool isBST(BinaryTree* root){
    int data = root->data;
        bool flag = true;
    stack<BinaryTree*> s;
    BinaryTree* cur = root;
        while(cur||!s.empty()){
            if(cur->lchild){
                if(cur->lchild->data < data){
                    s.push(cur);
                    cur = cur->lchild;
                    data = cur->data;
            }else{
                flag = false;
                break;
            }
        }else{
            cur = cur->rchild;
            if(cur){
                if(cur->data > data){
                    data = cur->data;
                }else{
                    flag = false;
                    break;
                }   
            }
            while(!cur&&!s.empty()){
                cur = s.top();
                s.pop();
                cur = cur->rchild;
                data = cur->data;
            } 
        }
    }
    return flag;
}            

复制