CC150 17.13

17_13.cpp

/* CC150 17.13 */
// convert a binary search tree (implemented with BiNode) into a doubly linked list
// the values should be kept in order and the operation should be performed in place

#include <iostream>

using namespace std;

struct BiNode {
	BiNode() : data(0), node1(nullptr), node2(nullptr) {}
	BiNode(int n) : data(n), node1(nullptr), node2(nullptr) {}
	int data;
	BiNode *node1, *node2;
};

// given the root of a binary search tree, convert to a doubly linked list and return the head
BiNode *convertBSTtoDLL(BiNode *root)
{
	if (!root)
		return root;
	BiNode *start = root;
	if (root->node1) { // convert left sub-tree
		root->node1 = convertBSTtoDLL(root->node1);
		start = root->node1;
		while (root->node1->node2) // let node1 point to the end of the left sub-list
			root->node1 = root->node1->node2;
		root->node1->node2 = root; // link the end of left sub-list to the root
	}
	if (root->node2) { // convert the right sub-tree
		root->node2 = convertBSTtoDLL(root->node2); // let node2 point to the start of the right sub-list
		root->node2->node1 = root; // link the start of right sub-list to the root
	}
	return start; // if left sub-tree exists, start points to the start of left sub-list, else it points to root
}

// build the linked list as a circular list
// ORDER MATTERS!!!
BiNode *convertCircular(BiNode *root)
{
	if (!root)
		return root;
	BiNode *leftHead = convertCircular(root->node1);
	BiNode *rightHead = convertCircular(root->node2);
	BiNode *head = leftHead ? leftHead : root;
	BiNode *tail = rightHead ? rightHead->node1 : root;
	if (leftHead) {
		root->node1 = leftHead->node1;
		root->node1->node2 = root;
	}
	if (rightHead) {
		root->node2 = rightHead;
		root->node2->node1 = root;
	}
	head->node1 = tail;
	tail->node2 = head; 
	return head;
}

BiNode *convertBSTtoDLL2(BiNode *root) {
	BiNode *head = convertCircular(root);
	head->node1->node2 = nullptr;
	head->node1 = nullptr;
	return head;
}

// insert data into the binary search tree
void insert(int data, BiNode *root) {
	if (data <= root->data) { // insert into left sub-tree
		if (root->node1)
			insert(data, root->node1);
		else
			root->node1 = new BiNode(data);
	}
	else { // insert into right sub-tree
		if (root->node2)
			insert(data, root->node2);
		else
			root->node2 = new BiNode(data);
	}
}

// print the binary search tree in order
void displayBST(BiNode *root) {
	if (!root)
		return;
	if (root->node1)
		displayBST(root->node1);
	cout << root->data << " ";
	if (root->node2)
		displayBST(root->node2);
}

// print the doubly linked list in order
void displayDLL(BiNode *root) {
	while (root) {
		cout << root->data << " ";
		root = root->node2;
	}
}

int main()
{
	BiNode *root = nullptr;
	int data;
	if (cin >> data) {
		root = new BiNode(data);
		while (cin >> data)
			insert(data, root);
	}
	displayBST(root);
	cout << endl;
	root = convertBSTtoDLL2(root);
	displayDLL(root);
	cout << endl;
	return 0;
}