Scribd
Upload
9 views

P6

Uploaded by

jaywareg003
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
9 views

P6

Uploaded by

jaywareg003
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

Name : Tejas Gitkhane

Roll no. : S511042


Class : SE

Div. :A

Batch : A2
Experiment 6
Implement Inordered binary tree and traverse it in in-order and pre-order

#include <iostream> using


namespace std;

// Node structure for Threaded Binary Tree struct


ThreadedNode {

int data;

ThreadedNode *left, *right;


bool isLeftThread, isRightThread;

ThreadedNode(int val) : data(val), left(nullptr), right(nullptr),


isLeftThread(false), isRightThread(false) {} };

// Class to represent the Threaded Binary Tree


class ThreadedBinaryTree { private:

ThreadedNode *root;

// Helper function to create a new threaded node


ThreadedNode* insert(ThreadedNode* root, int data) {
if (root == nullptr) {

return new ThreadedNode(data);

}
if (data < root->data) {
root->left = insert(root->left, data);

} else {

root->right = insert(root->right, data);

return root;

// Function to create threads void


createThreads(ThreadedNode* node) {

if (node == nullptr) return;

if (node->left) {
createThreads(node->left);

// Create right thread if


(node->right) {
createThreads(node->right);

// Creating threads if (node-


>left == nullptr) { node-
>isLeftThread = true; node->left
= predecessor(node);

if (node->right == nullptr) { node-


>isRightThread = true; node->right =
successor(node);

}
// Find the predecessor

ThreadedNode* predecessor(ThreadedNode* node) {

ThreadedNode* temp = node->left;


while (temp && !temp->isRightThread) {
temp = temp->right;

return temp;

// Find the successor

ThreadedNode* successor(ThreadedNode* node) {


ThreadedNode* temp = node->right; while (temp
&& !temp->isLeftThread) { temp = temp->left;

return temp;

public:

ThreadedBinaryTree() : root(nullptr) {}

// Insert function void


insert(int data) { root =
insert(root, data);
createThreads(root);

// In-order traversal void


inOrderTraversal() {
ThreadedNode* current = root;
while (current != nullptr) {

while (current->left != nullptr && !current->isLeftThread) {


current = current->left;
}

cout << current->data << " ";

// If there is a right thread, go to the right


if (current->isRightThread) {
current = current->right;

} else {

current = current->right;

while (current != nullptr && current->left != nullptr) {


current = current->left;

// Pre-order traversal void


preOrderTraversal() {
ThreadedNode* current = root;
while (current != nullptr) {
cout << current->data << " ";

// If left child is present

if (current->left != nullptr && !current->isLeftThread) {


current = current->left;

// If no left child, follow right thread


else if (current->isRightThread) {
current = current->right;

// Move to the next node

else {
while (current != nullptr && current->isRightThread) {
current = current->right;

if (current != nullptr) {
current = current->right;

}
}

};

// Main function to demonstrate the Threaded Binary Tree int


main() {

ThreadedBinaryTree tbt;

// Inserting values into the tree


tbt.insert(20); tbt.insert(10);
tbt.insert(30); tbt.insert(6);
tbt.insert(14); tbt.insert(24);
tbt.insert(36);

cout << "In-order Traversal: ";


tbt.inOrderTraversal(); cout
<< endl;

cout << "Pre-order Traversal: ";


tbt.preOrderTraversal(); cout
<< endl;

return 0;

}
OUTPUT:

You might also like