CC150 4.6

4_6.cpp

/* CC150 4.6
 * Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree.
 * You may assume that each node has a link to its parent.
 */

#include "detree.h"

using namespace std;

int main()
{
	detree tree;
	int key;
	while (cin >> key) // make sure the root has both left and right child!
		tree.insert(key);
	cout << "Binary tree in-order: " << endl;
	tree.dispInOrder(); cout << endl;
	cout << "Next node of " << tree.getRoot()->data << " is: "
		<< tree.getNext(tree.getRoot())->data << endl;
	cout << "Next node of " << tree.getRoot()->left->data << " is: "
		<< tree.getNext(tree.getRoot()->left)->data << endl;
	cout << "Next node of " << tree.getRoot()->right->data << " is: ";
	if (tree.getNext(tree.getRoot()->right) != nullptr)
		cout << tree.getNext(tree.getRoot()->right)->data << endl;
	else
		cout << "None!" << endl;
	return 0;
}

detree.h.cpp

/* CC150 4.6
 * Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree.
 * You may assume that each node has a link to its parent.
 */

#include <iostream>
using std::cout;

struct Node {
	int data;
	Node *left, *right;
	Node *parent;
};

class detree {
public:
	detree() : root(nullptr) {}
	~detree() { destroy(); };
	void insert(int key);
	void destroy() { destroy(root); }
	Node *getRoot() { return root; }
	Node *getNext(Node *leaf); // return the 'next' node of the given node in any binary tree
	void dispInOrder() { dispInOrder(root); }
private:
	Node *root;
	void insert(Node *leaf, int key);
	void destroy(Node *leaf);
	void dispInOrder(Node *leaf);
};

void detree::insert(int key)
{
	if (root == nullptr) { // initialize the root
		root = new Node;
		root->data = key;
		root->left = nullptr;
		root->right = nullptr;
		root->parent = nullptr;
	}
	else
		insert(root, key); // insert key into the tree
}

void detree::insert(Node *leaf, int key) // insert key under node leaf
{
	if (key <= leaf->data) { // key goes left if it's less than or equal to current node
		if (leaf->left == nullptr) { // creat new node if current node has no left child
			leaf->left = new Node;
			leaf->left->data = key;
			leaf->left->left = nullptr;
			leaf->left->right = nullptr;
			leaf->left->parent = leaf;
		}
		else
			insert(leaf->left, key); // insert into current node's left child
	}
	else { // key goes right if it's larger than current node
		if (leaf->right == nullptr) { // creat new node if current node has no right child
			leaf->right = new Node;
			leaf->right->data = key;
			leaf->right->left = nullptr;
			leaf->right->right = nullptr;
			leaf->right->parent = leaf;
		}
		else
			insert(leaf->right, key); // insert into current node's right child
	}
}

void detree::destroy(Node *leaf)
{
	if (leaf != nullptr) {
		destroy(leaf->left);
		destroy(leaf->right);
		delete leaf;
	}
}

Node *detree::getNext(Node *leaf)
{
	if (leaf == nullptr)
		return nullptr;
	if (leaf->right != nullptr) { // go right if the current node has a right child
		Node *next = leaf->right;
		while (next->left != nullptr) // search for the leftmost node in the right subtree of the current node
			next = next->left;
		return next;
	}
	else { // go back if the current node has no right child
		Node *curr = leaf;
		while (curr->parent != nullptr && curr != curr->parent->left) // curr is not the left child of its parent
			curr = curr->parent;
		if (curr->parent != nullptr)
			return curr->parent;
		else // the current node is already the last one in the tree
			return nullptr;
	}
}

void detree::dispInOrder(Node *leaf)
{
	if (leaf == nullptr)
		return;
	dispInOrder(leaf->left);
	cout << leaf->data << " ";
	dispInOrder(leaf->right);
}