資料結構
網路
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 Return 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 Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary 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 Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary Tree is not a BST"<<endl;
return 0;
}輸出
The Given Binary Tree is not a BST The Given Binary Tree is a BST
更新於： 30-Jul-2019
815 次瀏覽
廣告