判斷二叉樹是否為二叉搜尋樹

概要

這題利用二叉搜尋樹的特性：左子樹的所有的關鍵字小于根節點的關鍵字，右子樹的所有關鍵字都大于根結點 的關鍵字。二叉搜尋樹的中序周遊一定是個有序序列。根據這一特性可以利用二叉樹的非遞歸中序周遊來解答這個問題。

二叉樹資料結構

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;
}            

複制