どのように1本の木がBSTの木であることを判断します

まず考えたのはBSTツリーの性質を利用して--中序は遍歴して増加して、しかし私は今まだこのように判断することができるかどうかを確定することができなくて、まずこのようなアルゴリズムを1種のアルゴリズムとして計算して、間違っているならば、みんなに助けてもらいます:)
1.中間パスの増加
アイデア:デュアルポインタを使用して、1つは前駆者を指し、1つは現在のノードを指し、彼らのサイズを比較します.

bool isBST(Node * node)

{

        if ( node== NULL)

              return true;

 

        //             ，   false

        if (node->left != NULL && maxValue( node->left) > node->data)

              return false;

 

        //             ，   false

        if (node->right != NULL && minValue( node->right) < node->data)

              return false;

 

        //    

        if (!isBST(node->left) || !isBST( node->right))

              return false;

 

        //       ， BST

        returntrue;

}

時間複雑度:O(n)
2.利用定義:BSTツリーはツリー内のいずれかのノード要素がその左サブツリーのすべての要素よりも大きく、彼の右サブツリーのすべての要素よりも小さい【1つのノードが左子供より大きい右子供によってツリーがBSTツリーであると判断するのは間違いであることがわかる】
したがって,判定ノードは左サブツリーの最大値よりも大きく,右サブツリーの最小値よりも小さい.

bool isBST(Node * node)

{

        if ( node== NULL)

              return true;

 

        //             ，   false

        if (node->left != NULL && maxValue( node->left) > node->data)

              return false;

 

        //             ，   false

        if (node->right != NULL && minValue( node->right) < node->data)

              return false;

 

        //    

        if (!isBST(node->left) || !isBST( node->right))

              return false;

 

        //       ， BST

        returntrue;

}

3.
方法2ツリー内のデータの一部を繰り返すため,効率が低い.より良い方法は、ノードごとに1回しか遍歴しないことです.方法3の巧みな点は,サブツリーにおけるノード値の範囲を限定し,各ノードに1回しかアクセスできないことである.ノード値の初期範囲はINT_に限定することができるMINおよびINT_MAX.//BST bool isBST(Node*node){return(isBSTutil(node,INT_MIN,INT_MAX)}//2つのツリーで[min,max]の値範囲がある場合は、true bool isBSTutil(Node*node,int min,int max)コード実装を返します.
 
 
 
 
 
 

#include <iostream>

 

struct Node

{

        int key;

        Node*left;

        Node*right;

};

 

bool isBSTUtil(Node * node, int min, int max);

 

//     BST

bool isBST(Node * node )

{

       return(isBSTUtil( node, INT_MIN, INT_MAX));

}

 

//          ，     [min, max]，   true

bool isBSTUtil(Node * node , int min , int max )

{

        //    BST

        if (node == NULL)

              return true;

 

        //          /      ，   BST

        if (node->key < min || node->key > max)

              return false;

 

        //      

       return  isBSTUtil( node->left,min, node->key - 1) &&

             isBSTUtil( node->right, node->key + 1, max);

}

 

 

//       BST  

Node *createNewNode(int item )

{

        Node*temp = new Node;

      temp->key = item;

      temp->left = temp->right = NULL;

        returntemp;

}

 

 

int main()

{

    /* tree1   

            4

          /  

         2     5

        /

       1   3

    */

       Node*root = createNewNode(4);

      root->left = createNewNode(2);

      root->right = createNewNode(5);

      root->left->left = createNewNode(1);

      root->left->right = createNewNode(3);

 

        if(isBST(root))

             std::cout << tree1 is BST

;

        else

             std::cout << tree1 is not BST

;

 

        /* tree2   

            4

          /  

         2     5

        /     /

       1     3

       */

       root =createNewNode(4);

      root->left = createNewNode(2);

      root->left->left = createNewNode(1);

      root->right = createNewNode(5);

      root->right->left = createNewNode(3);

 

        if(isBST(root))

             std::cout << tree2 is BST

;

        else

             std::cout << tree2 is not BST

;

 

        return0;

}</iostream>