C++ Binary Search Tree Software Translated from Pascal Algorithms by James Pate Williams, Jr.

#pragma once
#include <cinttypes>
#include <vector>
using namespace std;

// See "Introduction to Algorithms"
// Thomas H. Cormen Among Others
// Chapter 13 Binary Search Trees
// Translated from Pascal found in
// "Applied Data Structures Using
// Pascal" by Guy J. Hale and
// Richard J. Easton Chapter 6
// Introduction to Trees

typedef struct treeNode
{
	uint32_t key;
	treeNode* lt, * rt;
} TREENODE, * PTREENODE;

class BinaryTree
{
public:
	static void InitTree(PTREENODE root, uint32_t key);
	static void InsertInTree(PTREENODE& root, uint32_t key);
	static void CreateTree(PTREENODE& root, vector<uint32_t> &data,
		unsigned int seed, size_t number);
	static void TravInOrder(PTREENODE node);
	static void TravPreOrder(PTREENODE node);
	static void TravPostOrder(PTREENODE node);
};

#include "BinaryTree.h"
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

void BinaryTree::InitTree(
	PTREENODE root, uint32_t key)
{
	root->key = key;
	root->lt = root->rt = NULL;
}

void BinaryTree::InsertInTree(
	PTREENODE& root, uint32_t key)
{
	bool inserted = false;
	PTREENODE node = new TREENODE();
	PTREENODE oneNode = root;
	
	while (!inserted)
	{
		if (key <= oneNode->key)
		{
			if (oneNode->lt != NULL)
				oneNode = oneNode->lt;
			else
			{
				oneNode->lt = node;
				inserted = true;
			}
		}

		else
		{
			if (oneNode->rt != NULL)
				oneNode = oneNode->rt;
			else
			{
				oneNode->rt = node;
				inserted = true;
			}
		}
	}

	node->key = key;
	node->lt = node->rt = NULL;
}

void BinaryTree::CreateTree(PTREENODE& root, vector<uint32_t>& data,
	unsigned int seed, size_t number)
{
	srand(seed);
	uint32_t key = rand() % 1000;

	data.push_back(key);
	root = new TREENODE();
	InitTree(root, key);

	for (size_t i = 1; i < number; i++)
	{
		bool found = false;
		uint32_t next = rand() % 1000;
		
		while (!found)
		{
			for (size_t j = 0; !found && j < data.size(); j++)
				found = data[j] == next;

			next = rand() % 1000;
		}

		data.push_back(next);
	}

	for (size_t i = 1; i < data.size(); i++)
	{
		BinaryTree::InsertInTree(root, data[i]);
	}
}

void BinaryTree::TravInOrder(PTREENODE node)
{
	if (node != NULL)
	{
		TravInOrder(node->lt);
		cout << node->key << endl;
		TravInOrder(node->rt);
	}
}

void BinaryTree::TravPreOrder(PTREENODE node)
{
	if (node != NULL)
	{
		cout << node->key << endl;
		TravPreOrder(node->lt);
		TravPreOrder(node->rt);
	}
}

void BinaryTree::TravPostOrder(PTREENODE node)
{
	if (node != NULL)
	{
		TravPostOrder(node->lt);
		TravPostOrder(node->rt);
		cout << node->key << endl;
	}
}

// DataStructuresFromPascal.cpp : This file contains the 'main'
// function. Program execution begins and ends there.
// James Pate Williams, Jr. (c) 2023

#include "BinaryTree.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	PTREENODE root = NULL;
	vector<uint32_t> data;
	unsigned int seed = 1;
	size_t number;

	cout << "# keys = ";
	cin >> number;
	cout << "PRNG seed = ";
	cin >> seed;
	cout << endl;
	BinaryTree::CreateTree(root, data, seed, number);
	BinaryTree::TravInOrder(root);
	cout << endl;
	BinaryTree::TravPreOrder(root);
}