//Check?if?a?binary?tree?is?binary?search?tree?or?not
#include?<stdio.h>
#include?<stdlib.h>
//#include?<stdint.h>
#include?<iostream>
#include?<queue>
#include?<climits>
using?namespace?std;
struct?BstNode
{
//int?data;
char?data;?
struct?BstNode?*left;
struct?BstNode?*right;
};
struct?BstNode?*GetNewNode(char?data)
{
//C++?-->BstNode?*newNode?=?new?BstNode();
BstNode?*newNode?=?(struct?BstNode*)malloc(sizeof(struct?BstNode));
newNode?->?data?=?data;
newNode?->?left?=?newNode?->?right?=?NULL;
return?newNode;
}
struct?BstNode?*Insert(struct?BstNode?*root,?char?data)
{
if?(root?==?NULL)//empty?tree
{
root?=?GetNewNode(data);
return?root;
}
else?if?(data?<=?root?->?data? )
{
root?->?left?=?Insert(root?->?left,?data);
}
else
{
root?->?right?=?Insert(root?->?right,?data);
}
return?root;
}
//Breadth-first
void?levelorder(struct?BstNode?*root)
{
if?(root?==?NULL)?return;
queue?<struct?BstNode*>?Q;
Q.push(root);
//while?there?is?at?least?one?discovered?node
while?(!Q.empty())
{
struct?BstNode?*current?=?Q.front();
cout<<current?->?data<<"?";
if?(current?->?left?!=?NULL)
{
Q.push(current?->?left);
}
if?(current?->?right?!=?NULL)
{
Q.push(current?->?right);
}
Q.pop();//removing?the?element?at?front
}
}
bool?IsBstUtil(struct?BstNode?*root,?int?minValue,?int?maxValue)
/*因為INT_MIN,?INT_MAX是正負(fù)無窮，所以我寫了int但是我要執(zhí)行的是char，按道理
應(yīng)該比較ascii碼，但是最終沒有輸出bool值，大神幫我解惑*/
{
if?(root?==?NULL)?return?true;
if?(root?->?data?>?minValue?&&?root?->?data?<?maxValue
&&?IsBstUtil(root?->?left,?minValue,?root?->?data)
&&?IsBstUtil(root?->?right,?root?->?data,?maxValue))
return?true;
else?return?false;
}
bool?IsBinarySearchTree(struct?BstNode?*root)
{
return?IsBstUtil(root,?INT_MIN,?INT_MAX);
}
int?main()
{
struct?BstNode?*root?=?NULL;//Creating?an?empty?tree
root?=?Insert(root,?'F');
root?=?Insert(root,?'D');
root?=?Insert(root,?'J');
root?=?Insert(root,?'B');
root?=?Insert(root,?'E');
root?=?Insert(root,?'G');
root?=?Insert(root,?'K');
root?=?Insert(root,?'A');
root?=?Insert(root,?'C');
root?=?Insert(root,?'I');
printf?("Levelorder-");
levelorder(root);
printf?("\n");
IsBinarySearchTree(root);//這里沒有按預(yù)期print出bool值
printf?("\n");
}因為INT_MIN, INT_MAX是正負(fù)無窮，所以我寫了int但是我要執(zhí)行的是char，按道理應(yīng)該比較ascii碼，但是最終沒有輸出bool值，大神幫我解惑
1 回答
已采納
onemoo
TA貢獻(xiàn)883條經(jīng)驗 獲得超454個贊
好像離你問問題已經(jīng)過去幾天了，你現(xiàn)在知道答案了嗎？
你算法寫得沒錯，其實答案很簡單：你根本就沒有 print ?。?/p>
IsBinarySearchTree(root) 函數(shù)只是返回一個 bool 類型值，That's all!
在這個函數(shù)前加上輸出語句吧：
std::cout << std::boolalpha <<?IsBinarySearchTree(root);
這樣就能打印出"true" or "false" 了。
P.S.?std::boolalpha 這個 manipulator 的功能是讓后面在打印 bool 值時打印出 true 或 false 的字符，否則會默認(rèn)打印出 1 或 0。
添加回答
舉報
0/150
提交
取消