//BSTNode.h
#include <iostream>
using namespace std;
class BSTNode
{
public:
int Key;
BSTNode *Left;
BSTNode *Right;
BSTNode *Parent;
BSTNode *root;
BSTNode * Insert(BSTNode * node, int key);
void Insert(int key);
void PrintTreeInOrder(BSTNode *node);
void PrintTree(); BSTNode *Search(BSTNode *node,int targetValue); void Search(int targetValue);
int FindMin(); int FindMax();
};
//BSTNode.cpp
#include <BSTNode.h>
BSTNode *BSTNode::Insert(BSTNode *node,int keyValue)
{
//IF BST doesn't exist,create a new node as root or it's reached when there's no any child node
//so we can insert a new node here
if(node==NULL)
{
node=new BSTNode;
node->Key=keyValue;
node->Left=NULL;
node->Right=NULL;
node->Parent=NULL;
}
//If the given key is greater than node's key then go to right subtree
else if(node->Key<keyValue)
{
node->Right=Insert(node->Right,keyValue);
node->Right->Parent=node;
}
//If the given key is smaller than node's key then go to the left subtree
else
{
node->Left=Insert(node->Left,keyValue);
node->Left->Parent=node;
}
return node;
}
void BSTNode::Insert(int key)
{
//Invoking Insert(BSTNode *node,int keyValue) function and passing root node and given key
root=Insert(root,key);
}
void BSTNode::PrintTreeInOrder(BSTNode *node)
{
//Stop printing if no node found
if(node==NULL)
{
return;
}
//Get the smallest key first which is the left subtree
PrintTreeInOrder(node->Left);
//Print the key
std::cout<<node->Key<<"t";
//Continue to the greates key which is in the right subtree
PrintTreeInOrder(node->Right);
}
void BSTNode::PrintTree()
{
PrintTreeInOrder(root);
cout<<"nFinished in PrintTree()"<<endl;
}
BSTNode BSTNode::Search(BSTNode node, int targetValue)
{
//The given target value is not found in BST
if (node == NULL)
{
return NULL;
}
//The given key is found
else if (node->Key == targetValue)
{
return node;
}
//The given key is greater than current node's key
else if (node->Key < targetValue)
{
return Search(node->Right, targetValue);
}
//The given key is smaller than current node's key
else
return Search(node->Left, targetValue);
}
void BSTNode::Search(int targetValue)
{
//Invoking Search() operation and passing root node
BSTNode *result = Search(root, targetValue);
if (result != NULL)
{
cout << "Found and resut.Key=" << result->Key << endl;
}
else
{
cout << "Not found " << targetValue << " in BSTNode" << endl;
}
}
int BSTNode::FindMin(BSTNode *node)
{
if (node == NULL)
{
return -1;
}
else if (node->Left == NULL)
{
return node->Key;
}
else
{
return FindMin(node->Left);
}
}
int BSTNode::FindMax(BSTNode *node)
{
if (node == NULL)
{
return -1;
}
else if (node->Right == NULL)
{
return node->Key;
}
else
{
return FindMax(node->Right);
}
}
int BSTNode::FindMin()
{
return FindMin(root);
}
int BSTNode::FindMax()
{
return FindMax(root);
}
//In main.cpp
#include <iostream>
#include <uuid/uuid.h>
#include <ctime>
#include <string.h>
#include <unistd.h>
#include <bits/stdc++.h>
#include <stack>
#include <BSTNode.h>
#include <random>
void bst9();
int main()
{
bst9();
return 0;
}
void bst9()
{
srand(time(NULL));
BSTNode bst;
for(int i=0;i<10;i++)
{
bst.Insert(rand()%1000000);
}
bst.PrintTree();
cout<<"Finished in bst9()"<<endl;
}
Comile as below
g++ -g -std=c++2a -I. h1.cpp BSTNode.cpp -o h1 -luuid
Run ./h1
Or get rid of reminder of 100000% when insert value into BST node
Run ./h1
The above two snapshots illustrates that the binary search tree is a sorted tree,the left is smallest,the root is middle,the right is the most biggest element in BST structure
#include <iostream>
#include <uuid/uuid.h>
#include <ctime>
#include <string.h>
#include "BSTNode.h"
#include <vector>
void BSTNodeSearch8();
int main()
{
BSTNodeSearch8();
return 0;
}
void BSTNodeSearch8()
{
BSTNode bst;
for(int i=0;i<100;i++)
{
bst.Insert(i*i*i);
}
bst.Search(98*98*98);
bst.Search(981*98*98);
cout<<"nFinished in BSTNodeSearch8()"<<endl;
}
Compile via below command
g++ -g -std=c++2a -I. h1.cpp BSTNode.cpp -o h1 -luuid
Run ./h1
void BSTFindMin9();
int main()
{
BSTFindMin9();
return 0;
}
void BSTFindMin9()
{
BSTNode bst;
for(int i=0;i<100;i++)
{
bst.Insert(i*i*i);
}
bst.PrintTree();
int min=bst.FindMin();
cout<<"Min="<<min<<endl;
int max=bst.FindMax();
cout<<"Max="<<max<<endl;
}
Compile
g++ -g -std=c++2a -I. h1.cpp BSTNode.cpp -o h1 -luuid
int BSTNode::Successor(BSTNode *node)
{
//The sucessor is the minimum key value of right subtree
if(node->Right!=NULL)
{
return FindMin(node->Right);
}
//If no any right subtree
else
{
BSTNode *parentNode=node->Parent;
BSTNode *currentNode=node;
//If currentNode is not root and currentNode is its right children continue moving up
while((parentNode!=NULL) && (currentNode==parentNode->Right))
{
currentNode=parentNode;
parentNode=currentNode->Parent;
}
//If parentNode is not null then the key of parentNode is the successor of node
return parentNode==NULL?-1:parentNode->Key;
}
}
int BSTNode::Successor(int key)
{
//Search the key's node first
BSTNode *keyNode=Search(root,key);
//Return the key.If the key is not found or successor is not found
return keyNode==NULL?-1:Successor(keyNode);
}
void Successor10();
int main()
{
Successor10();
return 0;
}
void Successor10()
{
BSTNode bst;
for(int i=0;i<100;i++)
{
bst.Insert(i*i*i);
}
int successor=bst.Successor(98*98*98);
cout<<"successor="<<successor<<endl; cout<<"Finished in Successor10()"<<endl;
}
Compile
g++ -g -std=c++2a -I. h1.cpp BSTNode.cpp -o h1 -luuid
Run ./h1
int BSTNode::Predecessor(BSTNode *node)
{
//The predecessor is the maximum key value of subtree
if(node->Left!=NULL)
{
return FindMax(node->Left);
}
//If no any left subtree
else
{
BSTNode *parentNode=node->Parent;
BSTNode *currentNode=node;
//If currentNode is not root and current node is its left children continue moving up
while((parentNode!=NULL)&&(currentNode==parentNode->Left))
{
currentNode=parentNode;
parentNode=currentNode->Parent;
}
//If parentNode is not NULL then the key of parentNode is the predecessor of node
return parentNode==NULL?-1:parentNode->Key;
}
}
int BSTNode::Predecessor(int key)
{
//Search the key's node first
BSTNode *keyNode=Search(root,key);
//Return the key
//If the key is not found or predecessor is not found,return -1
return keyNode==NULL?-1:Predecessor(keyNode);
}
void Predecessor11();
int main()
{
Predecessor11();
return 0;
}
void Predecessor11()
{
BSTNode bst;
for(int i=0;i<100;i++)
{
bst.Insert(i*i*i);
}
int predecessor=bst.Predecessor(98*98*98);
cout<<"predecessor="<<predecessor<<endl;
cout<<"Finished in Predecessor11()"<<endl;
}
Compile
g++ -g -std=c++2a -I. h1.cpp BSTNode.cpp -o h1 -luuid
Run ./h1
原文链接: https://www.cnblogs.com/Fred1987/p/15781460.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/184272
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
