Question: How to verify whether a binary tree is a binary search tree?
For example, the tree in Figure 1 is a binary search tree.
 |
| Figure 1: A binary search tree |
A node in binary tree is defined as:
struct BinaryTreeNode
{
int nValue;
BinaryTreeNode* pLeft;
BinaryTreeNode* pRight;
};
$ cat verify_binary.h
#include <iostream>
using namespace std;
class VerifyBTree {
public:
struct BinaryTreeNode
{
int nValue;
BinaryTreeNode* pLeft;
BinaryTreeNode* pRight;
};
VerifyBTree();
~VerifyBTree();
void verify();
void printTree();
private:
BinaryTreeNode *proot;
int VerifyBinaryTree(BinaryTreeNode *curNode);
void assignLeftRightValue(BinaryTreeNode *curNode, int value, BinaryTreeNode *left, BinaryTreeNode *right);
};
void VerifyBTree::assignLeftRightValue(BinaryTreeNode *curNode, int value, BinaryTreeNode *left, BinaryTreeNode *right) {
if (!curNode) {
return;
}
curNode->nValue = value;
curNode->pLeft = left;
curNode->pRight = right;
}
/*
10
6 14
4 8 12 16
*/
VerifyBTree::VerifyBTree() {
proot = new BinaryTreeNode[7];
assignLeftRightValue(&proot[0], 10, &proot[1], &proot[2]);
assignLeftRightValue(&proot[1], 6, &proot[3], &proot[4]);
assignLeftRightValue(&proot[2], 14, &proot[5], &proot[6]);
assignLeftRightValue(&proot[3], 4, NULL, NULL);
assignLeftRightValue(&proot[4], 8, NULL, NULL);
assignLeftRightValue(&proot[5], 12, NULL, NULL);
assignLeftRightValue(&proot[6], 16, NULL, NULL);
}
VerifyBTree::~VerifyBTree() {
if (proot) {
delete[] proot;
}
}
void VerifyBTree::verify() {
int ret = VerifyBinaryTree(proot);
if (ret > 0) {
cout << " all the elements are passed!" << endl;
}
}
// recursively check
int VerifyBTree::VerifyBinaryTree(BinaryTreeNode *curNode){
// check left
if (curNode->pLeft) {
if (curNode->nValue < curNode->pLeft->nValue) {
cout << curNode->nValue << " & left " << curNode->pLeft->nValue << " is wrong!" << endl;
return -1;
}
if (VerifyBinaryTree(curNode->pLeft) < 0) {
return -1;
}
}
// check right
if (curNode->pRight) {
if (curNode->nValue > curNode->pRight->nValue) {
cout << curNode->nValue << " & right " << curNode->pRight->nValue << " is wrong!" << endl;
return -1;
}
if (VerifyBinaryTree(curNode->pRight) < 0) {
return -1;
}
}
return 1;
}
void VerifyBTree::printTree() {
for (int i=0; i<7; i++) {
cout << proot[i].nValue << " ";
}
cout << endl;
}
$ cat verify_binary.cpp
#include "verify_binary.h"
int main(int argc, char **argv)
{
VerifyBTree myBTree;
myBTree.printTree();
myBTree.verify();
return 0;
}
Result:
10 6 14 4 8 12 16
all the elements are passed!
沒有留言:
張貼留言