資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究用 C++ 檢查給定的二叉樹是否為二叉查詢樹
二叉查詢樹是一種二叉樹資料結構，其中具有 3 個特性
二叉查詢樹的節點的左子樹僅包含鍵值小於節點鍵值的節點。
二叉查詢樹節點的右子樹僅包含鍵值大於節點鍵值的節點。
子樹的左子樹和右子樹每個都必須同時為二叉查詢樹。
演算法
Begin function BSTUtill() If node is equals to NULL then Returns 1. If data of node is less than minimum or greater than maximum data then Return 0. Traverse left and right sub-trees recursively. End.
示例程式碼
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
struct n {
int d;
n* l;
n* r;
};
int BSTUtil(n* node, int min, int max);
int isBST(n* node) {
return(BSTUtil(node, INT_MIN, INT_MAX));
}
int BSTUtil(struct n* node, int min, int max) {
if (node==NULL)
return 1;
if (node->d < min || node->d > max)
return 0;
return BSTUtil(node->l, min, node->d - 1) && BSTUtil(node->r, node->d + 1, max);
}
n* newN(int d) {
n* nod = new n;
nod->d = d;
nod->l = NULL;
nod->r = NULL;
return nod;
}
int main() {
n *root = newN(7);
root->l = newN(6);
root->r = newN(10);
root->l->l = newN(2);
root->l->r = newN(4);
if (isBST(root))
cout<<"The Given Tree is a BST"<<endl;
else
cout<<"The Given Tree is not a BST"<<endl;
n *root1 = newN(10);
root1->l = newN(6);
root1->r = newN(11);
root1->l->l = newN(2);
root1->l->r = newN(7);
if (isBST(root1))
cout<<"The Given Tree is a BST"<<endl;
else
cout<<"The Given Tree is not a BST"<<endl;
return 0;
}輸出
The Given Tree is not a BST The Given Tree is a BST
更新於: 30-7-2019
271 次瀏覽
廣告