資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C語言程式：檢查二叉樹是否為二叉搜尋樹 (BST)
二叉樹是一種樹形資料結構，其中每個節點有兩個子節點。這兩個子節點分別稱為左子節點和右子節點。
BST（二叉搜尋樹）是一種樹形結構，其中左子樹包含小於根節點的值，右子樹包含大於根節點的值。
在這裡，我們將檢查一個二叉樹是否為BST。
要檢查這一點，我們必須檢查二叉樹上的BST條件。對於根節點，檢查左子節點是否小於根節點，右子節點是否大於根節點，這適用於樹中所有存在子節點的節點。
檢查二叉樹是否為BST的程式
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int isBSTUtil(node* node, int min, int max);
int isBST(node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(node* node, int min, int max) {
if (node==NULL)
return 1;
if (node->data < min || node->data > max)
return 0;
return
isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max);
}
int main() {
node *root = new node(8);
root->left = new node(3);
root->right = new node(10);
root->left->left = new node(1);
root->left->right = new node(6);
if(isBST(root))
cout<<"The given tree is a BST";
else
cout<<"The given tree is Not a BST";
return 0;
}輸出
The given tree is a BST
程式碼解釋
上面的程式碼檢查是否為BST。main方法建立一棵樹並呼叫isBST()方法。此方法使用isBSTuntil()方法檢查左子節點和右子節點是否遵循BST規則，以及是否也形成了BST的子樹。
更新於：2019年8月7日
瀏覽量：271
廣告