Exercises

Section 32.14 Exercises

These exercises use the same BSTNode structure as our basic binary search tree implementation. Here is the BSTNode definition:

🔗

Listing 32.14.1. BSTNode Declaration

🔗

struct BSTNode {
  // Store a value and two child pointers
  char value;
  BSTNode* left;
  BSTNode* right;
};

Checkpoint 32.14.1.

Implement getHeight to return the height of the subtree rooted at the given node.

🔗

#include <iostream>
#include <string>
using namespace std;

struct BSTNode {
  // Store a value and two child pointers
  char value;
  BSTNode* left;
  BSTNode* right;

///-------------------------------------------------------
  ///  Everything else just to provide tracking of nodes
  ///-------------------------------------------------------

// Constructor - left/right set to null
  BSTNode(char val);

// Disable copy/assignment - these are declared but not defined
  BSTNode(const BSTNode& val);
  BSTNode& operator=(const BSTNode& val);

// Destructor - decrement counter
  ~BSTNode();

// Debugging purposes only - Not a normal feature
  //   Used for tracking memory allocation, updated in constructor/destructor
  static int nodeCount;
};

int BSTNode::nodeCount = 0;

BSTNode::BSTNode(char val) {
  value = val;
  left = nullptr;
  right = nullptr;
  nodeCount++;
}

BSTNode::~BSTNode() {
  nodeCount--;
}

class CharBST {
  // Would normally be private.
  // Made public to allow intrusive unit tests.
public:
  BSTNode* root;

public:
  /// Constructor - root inited to null
  CharBST();
  /// Destructor - deletes any child nodes
  ~CharBST();

/// return true if no values in tree
  bool isEmpty();

/// Produce an in order string representation
  std::string toString() const;

/// check if value is present
  bool containsRecursive(char val) const;
  bool containsIterative(char val) const;

/// add (a possibly duplicate) value to tree
  void insertRecursive(char val);
  void insertIterative(char val);

/// remove indicated char from tree
  void remove(char val);
  /// remove the smallest value from the tree
  void removeSmallest();
  
  /// Disable copy/assignment - these are declared but not defined
  CharBST(const CharBST& val);
  CharBST& operator=(const CharBST& val);
};

///----------------------Forward declare helpers---------------------
char smallestValueFrom(BSTNode* curNode);
BSTNode* removeSmallestHelper(BSTNode* startNode);
void deleteSubTree(BSTNode* curNode);
BSTNode* copySubTree(BSTNode* currentNode);

///----------------------CON/DE STRUCTORS----------------------------
CharBST::CharBST() {
  root = nullptr;
}

void deleteSubTree(BSTNode* curNode) {
  if (curNode != nullptr) {
    deleteSubTree(curNode->left);
    deleteSubTree(curNode->right);
    delete curNode;
  }
}

CharBST::~CharBST() {
  deleteSubTree(root);
  root = nullptr;
}

CharBST::CharBST(const CharBST& other) {
  root = copySubTree(other.root);
}

CharBST& CharBST::operator=(const CharBST& other) {
  if (this != &other) {
    // remove any existing nodes
    deleteSubTree(root);
    // copy nodes of other tree
    root = copySubTree(other.root);
  }
  return *this;
}

bool CharBST::isEmpty() {
  return root == nullptr;
}

///----------------------Print----------------------------
/// Nonmember helper function
string toStringHelper(BSTNode* curNode) {
  if (curNode == nullptr)
    return "";

string result = toStringHelper(curNode->left);
  result += to_string(curNode->value) + " ";
  result += toStringHelper(curNode->right);

return result;
}

string CharBST::toString() const {
  return toStringHelper(root);
}

///----------------------Search---------------------------

///----------------------RemoveSmallest---------------------------

///----------------------Smallest---------------------------

///----------------------Removal---------------------------

BSTNode* copySubTree(BSTNode* currentNode) {
  // TODO - FIXME
  return nullptr;
}
^^^^
int getHeight(BSTNode* node) {
    //TODO - fixme!
    return 0;
}
===!

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

/* Adds test data to produce this tree:
 *         _G_
 *        /   \
 *       C     P
 *      / \   / \
 *     B   F J   Y
 *            \
 *             M
 */

void insertTestData(CharBST& c) {
  c.root = nullptr; // remove (and leak!!!) any existing nodes

c.root = new BSTNode('G');

c.root->left = new BSTNode('C');
  c.root->left->left = new BSTNode('B');
  c.root->left->right = new BSTNode('F');

c.root->right = new BSTNode('P');
  c.root->right->right = new BSTNode('Y');
  c.root->right->left = new BSTNode('J');
  c.root->right->left->right = new BSTNode('M');
}

TEST_CASE("Height") {
  CharBST bst;
  insertTestData(bst);

int FHeight = getHeight(bst.root->left->right);
  REQUIRE(FHeight == 0);

int JHeight = getHeight(bst.root->right->left);
  REQUIRE(JHeight == 1);

int fullHeight = getHeight(bst.root);
  REQUIRE(fullHeight == 3);
}

🔗

Checkpoint 32.14.2.

Implement rotateRight to perform a right rotation on the subtree rooted at the given node. It should return the new root of the rotated subtree.

🔗

#include <iostream>
#include <string>
using namespace std;

struct BSTNode {
  // Store a value and two child pointers
  char value;
  BSTNode* left;
  BSTNode* right;

///-------------------------------------------------------
  ///  Everything else just to provide tracking of nodes
  ///-------------------------------------------------------

// Constructor - left/right set to null
  BSTNode(char val);

// Disable copy/assignment - these are declared but not defined
  BSTNode(const BSTNode& val);
  BSTNode& operator=(const BSTNode& val);

// Destructor - decrement counter
  ~BSTNode();

// Debugging purposes only - Not a normal feature
  //   Used for tracking memory allocation, updated in constructor/destructor
  static int nodeCount;
};

int BSTNode::nodeCount = 0;

BSTNode::BSTNode(char val) {
  value = val;
  left = nullptr;
  right = nullptr;
  nodeCount++;
}

BSTNode::~BSTNode() {
  nodeCount--;
}

class CharBST {
  // Would normally be private.
  // Made public to allow intrusive unit tests.
public:
  BSTNode* root;

public:
  /// Constructor - root inited to null
  CharBST();
  /// Destructor - deletes any child nodes
  ~CharBST();

/// return true if no values in tree
  bool isEmpty();

/// Produce an in order string representation
  std::string toString() const;

/// check if value is present
  bool containsRecursive(char val) const;
  bool containsIterative(char val) const;

/// add (a possibly duplicate) value to tree
  void insertRecursive(char val);
  void insertIterative(char val);

///----------------------CON/DE STRUCTORS----------------------------
CharBST::CharBST() {
  root = nullptr;
}

void deleteSubTree(BSTNode* curNode) {
  if (curNode != nullptr) {
    deleteSubTree(curNode->left);
    deleteSubTree(curNode->right);
    delete curNode;
  }
}

CharBST::~CharBST() {
  deleteSubTree(root);
  root = nullptr;
}

CharBST::CharBST(const CharBST& other) {
  root = copySubTree(other.root);
}

bool CharBST::isEmpty() {
  return root == nullptr;
}

///----------------------Print----------------------------
/// Nonmember helper function
string toStringHelper(BSTNode* curNode) {
  if (curNode == nullptr)
    return "";

string result = toStringHelper(curNode->left);
  result += to_string(curNode->value) + " ";
  result += toStringHelper(curNode->right);

return result;
}

string CharBST::toString() const {
  return toStringHelper(root);
}

///----------------------Search---------------------------

///----------------------RemoveSmallest---------------------------

///----------------------Smallest---------------------------

///----------------------Removal---------------------------

BSTNode* copySubTree(BSTNode* currentNode) {
  // TODO - FIXME
  return nullptr;
}
^^^^
BSTNode* rotateRight(BSTNode* parent) {
  /// TODO - fixme
  return nullptr;
}
===!

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

/* Adds test data to produce this tree:
 *         _G_
 *        /   \
 *       C     P
 *      / \   / \
 *     B   F J   Y
 *            \
 *             M
 */

void insertTestData(CharBST& c) {
  c.root = nullptr; // remove (and leak!!!) any existing nodes

c.root = new BSTNode('G');

c.root->left = new BSTNode('C');
  c.root->left->left = new BSTNode('B');
  c.root->left->right = new BSTNode('F');

c.root->right = new BSTNode('P');
  c.root->right->right = new BSTNode('Y');
  c.root->right->left = new BSTNode('J');
  c.root->right->left->right = new BSTNode('M');
}

TEST_CASE("RotateRightAtC") {
  CharBST bst;
  insertTestData(bst);

BSTNode* target = bst.root->left;

BSTNode* newParent = rotateRight(target);

REQUIRE(newParent->value == 'B');
  REQUIRE(newParent->right->value == 'C');
  REQUIRE(newParent->right->left == nullptr);
}

TEST_CASE("RotateRightAtG") {
  CharBST bst;
  insertTestData(bst);

BSTNode* target = bst.root;

BSTNode* newParent = rotateRight(target);

REQUIRE(newParent->value == 'C');
  REQUIRE(newParent->right->value == 'G');
  REQUIRE(newParent->right->left->value == 'F');
}

🔗

Checkpoint 32.14.3.

Implement rotateLeft to perform a left rotation on the subtree rooted at the given node. It should return the new root of the rotated subtree.

🔗

#include <iostream>
#include <string>
using namespace std;

struct BSTNode {
  // Store a value and two child pointers
  char value;
  BSTNode* left;
  BSTNode* right;

///-------------------------------------------------------
  ///  Everything else just to provide tracking of nodes
  ///-------------------------------------------------------

// Constructor - left/right set to null
  BSTNode(char val);

// Disable copy/assignment - these are declared but not defined
  BSTNode(const BSTNode& val);
  BSTNode& operator=(const BSTNode& val);

// Destructor - decrement counter
  ~BSTNode();

// Debugging purposes only - Not a normal feature
  //   Used for tracking memory allocation, updated in constructor/destructor
  static int nodeCount;
};

int BSTNode::nodeCount = 0;

BSTNode::BSTNode(char val) {
  value = val;
  left = nullptr;
  right = nullptr;
  nodeCount++;
}

BSTNode::~BSTNode() {
  nodeCount--;
}

class CharBST {
  // Would normally be private.
  // Made public to allow intrusive unit tests.
public:
  BSTNode* root;

public:
  /// Constructor - root inited to null
  CharBST();
  /// Destructor - deletes any child nodes
  ~CharBST();

/// return true if no values in tree
  bool isEmpty();

/// Produce an in order string representation
  std::string toString() const;

/// check if value is present
  bool containsRecursive(char val) const;
  bool containsIterative(char val) const;

/// add (a possibly duplicate) value to tree
  void insertRecursive(char val);
  void insertIterative(char val);

///----------------------CON/DE STRUCTORS----------------------------
CharBST::CharBST() {
  root = nullptr;
}

void deleteSubTree(BSTNode* curNode) {
  if (curNode != nullptr) {
    deleteSubTree(curNode->left);
    deleteSubTree(curNode->right);
    delete curNode;
  }
}

CharBST::~CharBST() {
  deleteSubTree(root);
  root = nullptr;
}

CharBST::CharBST(const CharBST& other) {
  root = copySubTree(other.root);
}

bool CharBST::isEmpty() {
  return root == nullptr;
}

///----------------------Print----------------------------
/// Nonmember helper function
string toStringHelper(BSTNode* curNode) {
  if (curNode == nullptr)
    return "";

string result = toStringHelper(curNode->left);
  result += to_string(curNode->value) + " ";
  result += toStringHelper(curNode->right);

return result;
}

string CharBST::toString() const {
  return toStringHelper(root);
}

///----------------------Search---------------------------

///----------------------RemoveSmallest---------------------------

///----------------------Smallest---------------------------

///----------------------Removal---------------------------

BSTNode* copySubTree(BSTNode* currentNode) {
  // TODO - FIXME
  return nullptr;
}
^^^^
BSTNode* rotateLeft(BSTNode* parent) {
  /// TODO - fixme
  return nullptr;
}
===!

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

/* Adds test data to produce this tree:
 *         _G_
 *        /   \
 *       C     P
 *      / \   / \
 *     B   F J   Y
 *            \
 *             M
 */

void insertTestData(CharBST& c) {
  c.root = nullptr; // remove (and leak!!!) any existing nodes

c.root = new BSTNode('G');

c.root->left = new BSTNode('C');
  c.root->left->left = new BSTNode('B');
  c.root->left->right = new BSTNode('F');

c.root->right = new BSTNode('P');
  c.root->right->right = new BSTNode('Y');
  c.root->right->left = new BSTNode('J');
  c.root->right->left->right = new BSTNode('M');
}

TEST_CASE("RotateLeftAtC") {
  CharBST bst;
  insertTestData(bst);

BSTNode* target = bst.root->left;

BSTNode* newParent = rotateLeft(target);

REQUIRE(newParent->value == 'F');
  REQUIRE(newParent->left->value == 'C');
  REQUIRE(newParent->left->right == nullptr);
}

TEST_CASE("RotateLeftAtG") {
  CharBST bst;
  insertTestData(bst);

BSTNode* target = bst.root;

BSTNode* newParent = rotateLeft(target);

REQUIRE(newParent->value == 'P');
  REQUIRE(newParent->left->value == 'G');
  REQUIRE(newParent->left->right->value == 'J');
}

🔗

You have attempted of activities on this page.

🔗

Prev Top Next