在 c 中验证 BST 的最佳方法

用户8366698

我刚开始学习树木，我编写了代码来验证一棵树是否是 BST 的天气，我想知道是否有比我目前正在做的方法更好的方法来做到这一点。我现在这样做的方式是，我将每个节点中的所有值都推送到一个堆栈中，而不是通过该堆栈来检查每个值是否小于前一个值。我觉得现在代码的运行时间太高了，时间复杂度也太高了。

    // this code is to check if a binary tree is a BST

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 256

int A[MAX_SIZE];
int top;

typedef struct node{
    int data;
    struct node* right;
    struct node* left;
}node;

node* Insert(node* root, int data);
void Inorder(node* root);
node* GetNewNode(int data);

void Push(int x){
    A[++top] = x;
}

void Pop(){
    top--;
}

int Top(){
    return A[top];
}

int main(void){
    int data, x, lastValue;
    int BST;
    node* root = NULL;
    printf("how many elements would you like to be in the tree\n");
    scanf("%i", &x);
    for(int i = 0; i < x; i++){
        scanf("%i", &data);
        root = Insert(root, data);
    }
    Inorder(root);
    for(int i = 0; i < MAX_SIZE; i++){
        x = Top();
        if(i >= 1){
            if(top < 0){
                break;
            }
            if(lastValue > x){
                BST = 1;
            }
            else{
                BST = 0;
                break;
            }
        }

        lastValue = x;

        Pop();
    }
    if(!BST){
        printf("not a BST\n");
    }
    else{
        printf("BST\n");
    }
}

node* Insert(node* root, int data){
    if(root == NULL){
        root = GetNewNode(data);
    }
    else if(data <= root->data){
        root->left = Insert(root->left, data);
    }
    else{
        root->right= Insert(root->right, data);
    }
    return root;
}

node* GetNewNode(int data){
    node* newNode = (node*)malloc(sizeof(node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void Inorder(node* root){
    if(root == NULL){
        return;
    }
    Inorder(root->left);
    Push(root->data);
    Inorder( root->right);
}

穆罕默德·萨利赫

这是我如何做到的：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

int isBSTUtil(struct node* node, int min, int max);

/* Returns true if the given tree is a binary search tree 
 (efficient version). */
int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 

/* Returns true if the given tree is a BST and its 
   values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max) 
{ 
  /* an empty tree is BST */
  if (node==NULL) 
     return 1;

  /* false if this node violates the min/max constraint */ 
  if (node->data < min || node->data > max) 
     return 0; 

  /* otherwise check the subtrees recursively, 
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, node->data-1) &&  // Allow only distinct values
    isBSTUtil(node->right, node->data+1, max);  // Allow only distinct values
} 

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}

/* Driver program to test above functions*/
int main()
{
  struct node *root = newNode(4);
  root->left        = newNode(2);
  root->right       = newNode(5);
  root->left->left  = newNode(1);
  root->left->right = newNode(3); 

  if(isBST(root))
    printf("Is BST");
  else
    printf("Not a BST");

  getchar();
  return 0;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。