Binary Tree in C++ coding in the data structure

Dec 11, 20230 likes48 views

This document discusses binary trees and binary search trees in C++. It includes functions to create and traverse binary trees in preorder, inorder, and postorder fashion. For binary search trees, it includes functions to insert nodes, perform inorder traversal, find the minimum value node, and delete nodes. These data structures and functions provide ways to organize and manipulate tree-based data in C++ programs.

// Binary Tree in C++
#include <stdlib.h>
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
// New node creation
struct node *newNode(int data) {
struct node *node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Traverse Preorder
void traversePreOrder(struct node *temp) {
if (temp != NULL) {
cout << " " << temp->data;
traversePreOrder(temp->left);
traversePreOrder(temp->right);
}
}
// Traverse Inorder
void traverseInOrder(struct node *temp) {
if (temp != NULL) {
traverseInOrder(temp->left);
cout << " " << temp->data;
traverseInOrder(temp->right);
}
}
// Traverse Postorder
void traversePostOrder(struct node *temp) {
if (temp != NULL) {

traversePostOrder(temp->left);
traversePostOrder(temp->right);
cout << " " << temp->data;
}
}
int main() {
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
cout << "preorder traversal: ";
traversePreOrder(root);
cout << "nInorder traversal: ";
traverseInOrder(root);
cout << "nPostorder traversal: ";
traversePostOrder(root);
}
// Binary Search Tree operations in C++
#include <iostream>
using namespace std;
struct node {
int key;
struct node *left, *right;
};
// Create a node
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Inorder Traversal
void inorder(struct node *root) {
if (root != NULL) {
// Traverse left
inorder(root->left);

// Traverse root
cout << root->key << " -> ";
// Traverse right
inorder(root->right);
}
}
// Insert a node
struct node *insert(struct node *node, int key) {
// Return a new node if the tree is empty
if (node == NULL) return newNode(key);
// Traverse to the right place and insert the node
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// Find the inorder successor
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current;
}
// Deleting a node
struct node *deleteNode(struct node *root, int key) {
// Return if the tree is empty
if (root == NULL) return root;
// Find the node to be deleted
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// If the node is with only one child or no child
if (root->left == NULL) {

struct node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct node *temp = root->left;
free(root);
return temp;
}
// If the node has two children
struct node *temp = minValueNode(root->right);
// Place the inorder successor in position of the node to be deleted
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Driver code
int main() {
struct node *root = NULL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 7);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 4);
cout << "Inorder traversal: ";
inorder(root);
cout << "nAfter deleting 10n";
root = deleteNode(root, 10);
cout << "Inorder traversal: ";
inorder(root);
}

Solution : #include #include #include //------------------------------------------------- struct node { int data; struct node *next; }*start=NULL; //------------------------------------------------------------ void creat() { char ch; do { struct node *new_node,*current; new_node=(struct node *)malloc(sizeof(struct node)); printf(\"nEnter the data : \"); scanf(\"%d\",&new_node->data); new_node->next=NULL; if(start==NULL) { start=new_node; current=new_node; } else { current->next=new_node; current=new_node; } printf(\"nDo you want to creat another : \"); ch=getche(); }while(ch!=\'n\'); } //------------------------------------------------------------------ void display() { struct node *new_node; printf(\"The Linked List : n\"); new_node=start; while(new_node!=NULL) { printf(\"%d--->\",new_node->data); new_node=new_node->next; } printf(\"NULL\"); } //---------------------------------------------------- void main() { create(); display(); } //---------------------------------------------------- Output : #include #include #include #include struct node { int data; int key; struct node *next; struct node *prev; }; //this link always point to first Link struct node *head = NULL; //this link always point to last Link struct node *last = NULL; struct node *current = NULL; //is list empty bool isEmpty(){ return head == NULL; } int length(){ int length = 0; struct node *current; for(current = head; current != NULL; current = current->next){ length++; } return length; } //display the list in from first to last void displayForward(){ //start from the beginning struct node *ptr = head; //navigate till the end of the list printf(\"\ [ \"); while(ptr != NULL){ printf(\"(%d,%d) \",ptr->key,ptr->data); ptr = ptr->next; } printf(\" ]\"); } //display the list from last to first void displayBackward(){ //start from the last struct node *ptr = last; //navigate till the start of the list printf(\"\ [ \"); while(ptr != NULL){ //print data printf(\"(%d,%d) \",ptr->key,ptr->data); //move to next item ptr = ptr ->prev; printf(\" \"); } printf(\" ]\"); } //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()){ //make it the last link last = link; }else { //update first prev link head->prev = link; } //point it to old first link link->next = head; //point first to new first link head = link; } //insert link at the last location void insertLast(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()){ //make it the last link last = link; }else { //make link a new last link last->next = link; //mark old last node as prev of new link link->prev = last; } //point last to new last node last = link; } //delete first item struct node* deleteFirst(){ //save reference to first link struct node *tempLink = head; //if only one link if(head->next == .

Linked listsGeorge Scott IV

The document contains C++ code for implementing and testing various operations on linked lists, including adding/deleting nodes, sorting, splitting lists, reversing lists, and checking for circularity. It defines a Node struct with data and next pointer, and includes functions for initializing nodes, adding/deleting nodes, sorting, splitting, reversing lists, checking for circularity, and more. It also includes unit tests for various functions using the BOOST test framework.

Program to insert in a sorted list #includestdio.h#include.pdfsudhirchourasia86

* Program to insert in a sorted list */ #include #include /* Link list node */ struct node { int data; struct node* next; }; /* function to insert a new_node in a list. Note that this function expects a pointer to head_ref as this can modify the head of the input linked list (similar to push())*/ void sortedInsert(struct node** head_ref, struct node* new_node) { struct node* current; /* Special case for the head end */ if (*head_ref == NULL || (*head_ref)->data >= new_node->data) { new_node->next = *head_ref; *head_ref = new_node; } else { /* Locate the node before the point of insertion */ current = *head_ref; while (current->next!=NULL && current->next->data < new_node->data) { current = current->next; } new_node->next = current->next; current->next = new_node; } } /* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */ /* A utility function to create a new node */ struct node *newNode(int new_data) { /* allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node)); /* put in the data */ new_node->data = new_data; new_node->next = NULL; return new_node; } /* Function to print linked list */ void printList(struct node *head) { struct node *temp = head; while(temp != NULL) { printf(\"%d \", temp->data); temp = temp->next; } } /* Drier program to test count function*/ int main() { /* Start with the empty list */ struct node* head = NULL; struct node *new_node = newNode(5); sortedInsert(&head, new_node); new_node = newNode(10); sortedInsert(&head, new_node); new_node = newNode(7); sortedInsert(&head, new_node); new_node = newNode(3); sortedInsert(&head, new_node); new_node = newNode(1); sortedInsert(&head, new_node); new_node = newNode(9); sortedInsert(&head, new_node); printf(\"\ Created Linked List\ \"); printList(head); return 0; } public class Listnode { //*** fields *** private Object data; private Listnode next; //*** methods *** // 2 constructors public Listnode(Object d) { this(d, null); } public Listnode(Object d, Listnode n) { data = d; next = n; } // access to fields public Object getData() { return data; } public Listnode getNext() { return next; } // modify fields public void setData(Object ob) { data = ob; } public void setNext(Listnode n) { next = n; } } Thsi below program print out all the varibles in SLL #include #include #include /* Link list node */ struct node { int data; struct node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Takes head pointer of the linked list and index as arguments and return data at index*/ int GetNth(struct node* head, int index) { struct node* current = head; int .

DS group binary tree all information M.pptxAjajKhan23

#include iostream using namespace std; const int nil = 0; cl.docxajoy21

The program implements a binary search tree to store 20 integers input by the user. It performs level order, preorder, inorder and postorder traversals of the tree, printing the value and level of each node. It also outputs the number of leaf nodes, nodes with one child, and nodes with two children. Finally, it calculates and prints the maximum and minimum leaf levels and checks if the tree is balanced.

create a binary search tree from an empty one by adding the key valu.pdferremmfab

create a binary search tree from an empty one by adding the key value alphabetically in c++ Solution //Binary Search Tree Program #include #include using namespace std; class BinarySearchTree { private: struct tree_node //structure to hold Binary search tree { tree_node* left; tree_node* right; int data; }; tree_node* root; public: BinarySearchTree() //constructor of Binary search tree { root = NULL; } //function declarations bool isEmpty() const { return root==NULL; } void print_inorder(); void inorder(tree_node*); void print_preorder(); void preorder(tree_node*); void print_postorder(); void postorder(tree_node*); void insert(int); void remove(int); }; // Smaller elements go left // larger elements go right void BinarySearchTree::insert(int d) //insert function to BST { tree_node* t = new tree_node; tree_node* parent; t->data = d; t->left = NULL; t->right = NULL; parent = NULL; // is this a new tree? if(isEmpty()) root = t; else { //Note: ALL insertions are as leaf nodes tree_node* curr; curr = root; // Find the Node\'s parent while(curr) { parent = curr; if(t->data > curr->data) curr = curr->right; else curr = curr->left; } if(t->data < parent->data) parent->left = t; else parent->right = t; } } void BinarySearchTree::remove(int d) { //Locate the element bool found = false; if(isEmpty()) { cout<<\" This Tree is empty! \"<data == d) { found = true; break; } else { parent = curr; if(d>curr->data) curr = curr->right; else curr = curr->left; } } if(!found) { cout<<\" Data not found! \"<left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL)) { if(curr->left == NULL && curr->right != NULL) { if(parent->left == curr) { parent->left = curr->right; delete curr; } else { parent->right = curr->right; delete curr; } } else // left child present, no right child { if(parent->left == curr) { parent->left = curr->left; delete curr; } else { parent->right = curr->left; delete curr; } } return; } //We\'re looking at a leaf node if( curr->left == NULL && curr->right == NULL) { if(parent->left == curr) parent->left = NULL; else parent->right = NULL; delete curr; return; } //Node with 2 children // replace node with smallest value in right subtree if (curr->left != NULL && curr->right != NULL) { tree_node* chkr; chkr = curr->right; if((chkr->left == NULL) && (chkr->right == NULL)) { curr = chkr; delete chkr; curr->right = NULL; } else // right child has children { //if the node\'s right child has a left child // Move all the way down left to locate smallest element if((curr->right)->left != NULL) { tree_node* lcurr; tree_node* lcurrp; lcurrp = curr->right; lcurr = (curr->right)->left; while(lcurr->left != NULL) { lcurrp = lcurr; lcurr = lcurr->left; } curr->data = lcurr->data; delete lcurr; lcurrp->left = NULL; } else { tree_node* tmp; tmp = curr->right; curr->data = tmp->data; curr->right = tmp->right; delete tmp; } } return; } } void BinarySearchTree::print_inorder() { inorder(root); } void BinarySearchTree::inorder(tree_node* p) .

Write a program that accepts an arithmetic expression of unsigned in.pdfJUSTSTYLISH3B2MOHALI

Write a program that accepts an arithmetic expression of unsigned integers in postfix notation and builds the arithmetic expression tree that represents that expression. From that tree, the corresponding fully parenthesized infix expression should be displayed and a file should be generated that contains the three address format instructions. This topic is discussed in the week 4 reading in module 2, section II-B. The main class should create the GUI shown below: Pressing the Construct Tree button should cause the tree to be constructed and using that tree, the corresponding infix expression should be displayed and the three address instruction file should be generated. The postfix expression input should not be required to have spaces between every token. Note in the above example that 9+- are not separated by spaces. The above example should produce the following output file containing the three address instructions: Add R0 5 9 Sub R1 3 R0 Mul R2 2 3 Div R3 R1 R2 Inheritance should be used to define the arithmetic expression tree. At a minimum, it should involve three classes: an abstract class for the tree nodes and two derived classes, one for operand nodes and another for operator nodes. Other classes should be included as needed to accomplish good object-oriented design. All instance data must be declared as private. You may assume that the expression is syntactically correct with regard to the order of operators and operands, but you should check for invalid tokens, such as characters that are not valid operators or operands such as 2a, which are not valid integers. If an invalid token is detected a RuntimeException should be thrown and caught by the main class and an appropriate error message should be displayed. Three Adddress Generator Enter Postfix Expression 359 2 3 Construct Tree Infix Expression ((3-(5 9))/ (2* 3 Solution #include #include #include #include #include struct TREE //Structure to represent a tree { char data; struct TREE *right,*left,*root; }; typedef TREE tree; /* Stack Using Linked List */ struct Stack //Structure to represent Stack { struct TREE *data; struct Stack *next,*head,*top; //Pointers to next node,head and top }; typedef struct Stack node; node *Nw; //Global Variable to represent node void initialize(node *&n) { n = new node; n -> next = n -> head = n -> top = NULL; } void create(node *n) { Nw = new node; //Create a new node Nw -> next = NULL; //Initialize next pointer field if(n -> head == NULL) //if first node { n -> head = Nw; //Initialize head n -> top = Nw; //Update top } } void push(node *n,tree *ITEM) { node *temp = n -> head; if(n -> head == NULL) //if First Item is Pushed to Stack { create(n); //Create a Node n -> head -> data = ITEM; //Insert Item to head of List n -> head = Nw; return; //Exit from Function } create(n); //Create a new Node Nw -> data = ITEM; //Insert Item while(temp -> next != NULL) temp = temp -> next; //Go to Last Node temp -> next = Nw; //Point New node n -> top = Nw; //Upda.

Write a C program that reads the words the user types at the command.pdfSANDEEPARIHANT

Write a C program that reads the words the user types at the command prompt (using the \'int argc, char * argv[] and store each unique letter in a Binary Search Tree. When a duplicate is encountered do not store the letter again and instead keep track of the count in the tree. Once the Binary Search tree has been created print out the tree both inorder and reverse order. Also print the highest and lowest alphabetically letter in the tree if any. Solution # include # include # include typedef struct BST { int data; struct BST *lchild, *rchild; } node; void insert(node *, node *); void preorder(node *); findMinimum(struct node* root) findMaximum(struct node* root) void reverseLevelOrder(struct node* root) void main(int argc,char argv) { char argv = \'N\'; int key; node *new_node, *root, *tmp, *parent; node *get_node(); root = NULL; clrscr(); printf(\"\ Program For Binary Search Tree \"); do { printf(\"\ 1.Create\"); printf(\"\ 2.Search\"); printf(\"\ 3.Recursive Traversals\"); printf(\"\ 4.Exit\"); printf(\"\ Enter your choice :\"); scanf(\"%d\", &argc); switch (argc) { case 1: do { new_node = get_node(); printf(\"\ Enter The Element \"); scanf(\"%d\", &new_node->data); if (root == NULL) /* Tree is not Created */ root = new_node; else insert(root, new_node); printf(\"\ Want To enter More Elements?(y/n)\"); argv= getch(); } while (argv == \'y\'); break; case 2: if (root == NULL) printf(\"Tree Is Not Created\"); else { printf(\"\ The Preorder display : \"); preorder(root); } break; } } while (argv != 4); } /* Get new Node */ node *get_node() { node *temp; temp = (node *) malloc(sizeof(node)); temp->lchild = NULL; temp->rchild = NULL; return temp; } /* This function is for creating a binary search tree */ void insert(node *root, node *new_node) { if (new_node->data < root->data) { if (root->lchild == NULL) root->lchild = new_node; return newNode(key); else insert(root->lchild, new_node); } if (new_node->data > root->data) { if (root->rchild == NULL) root->rchild = new_node; return newNode(key); else insert(root->rchild, new_node); } } if (key == node->key) { (node->count)++; return node; } /* This function displays the tree in preorder fashion */ void preorder(node *temp) { if (temp != NULL) { printf(\"%d\", temp->data); preorder(temp->lchild); preorder(temp->rchild); } } // Returns maximum value in a given Binary Tree int findMaximum(struct node* root) { // Base case if (root == NULL) return INT_MAXIMUM; // Return maximum of 3 values: // 1) Root\'s data 2) Max in Left Subtree // 3) Max in right subtree int res = root->data; int lres = findMaximum (root->lchild); int rres = findMaximum (root->rchild); if (lres > res) res = lres; if (rres > res) res = rres; return res; } // Returns minimum value in a given Binary Tree int findMinimum(struct node* root) { // Base case if (root == NULL) return INT_MINIMUM; // Return minimum of 3 values: // 1) Root\'s data 2) Max in Left Subtree // 3) Max in right subtree int res = root->data; int lres = findMinimum(r.

Data StructuresPlease I need help completing this c++ program..pdfarkleatheray

Data Structures Please I need help completing this c++ program. it was giving to complete it with no other discriptions. #include using namespace std; template struct node { datatype info; node *left, *right; }; template class tree { public: tree(); ~tree(); bool isempty(); void inserttree(datatype data); void print(); private: node *root; }; template tree::tree() { root = NULL; } template void tree ::inserttree(datatype data) { node *temp; temp = new node ; temp->left = NULL; temp->right = NULL; temp->info = data; if (root == NULL) root = temp; else before = NULL; after = root; while (after != NULL) { b = a; root ...; else } if(temp->info< before->info) before->left = temp; else before->right = temp; //before = after; //if (temp->info < after->info) //after = after->left; //else //after = after->right; //if(temp->info< before->info) //before->left = temp; //else //before->right = temp; } template void tree ::print(tree *temp) { if (temp != NULL) { print(temp->left); cout << temp->info << endl; print(temp->right); } p(); print(root); } int main() { tree t; //put this in a loop t.inserttree(90); t.inserttree(80); t.inserttree(108); t.p(); } Solution // HEADER FILE FOR BINARY TREE// // Define a structure to be used as the tree node struct TreeNode { int Key; float fValue; int iValue; char cArray[7]; TreeNode *left; TreeNode *right; }; class Code202_Tree { private: TreeNode *root; public: Code202_Tree(); ~Code202_Tree(); bool isEmpty(); TreeNode *SearchTree(int Key); bool Insert(TreeNode *newNode); bool Insert(int Key, float f, int i, char *cA); bool Delete(int Key); void PrintOne(TreeNode *T); void PrintTree(); private: void ClearTree(TreeNode *T); TreeNode *DupNode(TreeNode * T); void PrintAll(TreeNode *T); }; #endif //IMPLEMENTATION .CPP FILE FOR BINARY TREE// #include #include #include \"Code202_Tree.h\" using namespace std; //-------------------------------------------- // Function: Code202_Tree() // Purpose: Class constructor. //-------------------------------------------- Code202_Tree::Code202_Tree() { root = NULL; return; } //-------------------------------------------- // Function: Code202_Tree() // Purpose: Class destructor. //-------------------------------------------- Code202_Tree::~Code202_Tree() { ClearTree(root); return; } //-------------------------------------------- // Function: ClearTree() // Purpose: Perform a recursive traversal of // a tree destroying all nodes. //-------------------------------------------- void Code202_Tree::ClearTree(TreeNode *T) { if(T==NULL) return; // Nothing to clear if(T->left != NULL) ClearTree(T->left); // Clear left sub-tree if(T->right != NULL) ClearTree(T->right); // Clear right sub-tree delete T; // Destroy this node return; } //-------------------------------------------- // Function: isEmpty() // Purpose: Return TRUE if tree is empty. //-------------------------------------------- bool Code202_Tree::isEmpty() { return(root==NULL); } //-------------------------------------------- // Function.

AvlTree.h#ifndef AVL_TREE_H#define AVL_TREE_H#include d.docxrock73

AvlTree.h #ifndef AVL_TREE_H #define AVL_TREE_H #include "dsexceptions.h" #include <iostream> // For NULL #include <queue> // For level order printout #include <vector> #include <algorithm> // For max() function using namespace std; // AvlTree class // // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds // // ******************PUBLIC OPERATIONS********************* // Programming Assignment Part I // bool empty( ) --> Test for empty tree @ root // int size( ) --> Quantity of elements in tree // int height( ) --> Height of the tree (null == -1) // void insert( x ) --> Insert x // void insert( vector<T> ) --> Insert whole vector of values // void remove( x ) --> Remove x (unimplemented) // bool contains( x ) --> Return true if x is present // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void printTree( ) --> Print tree in sorted (in) order // void printPreOrder( ) --> Print tree in pre order // void printPostOrder( ) --> Print tree in post order // void printInOrder( ) --> Print tree in *in* order // Programming Assignment Part II (microassignment) // void makeEmpty( ) --> Remove and delete all items // void ~AvlTree( ) --> Big Five Destructor // AvlTree(const AvlTree &other) --> BigFive Copy Constructor // AvlTree(const AvlTree &&other) --> BigFive Move Constructor // AvlTree &operator= ( AvlTree & other ) --> Big Five Copy *assignment* operator // AvlTree &operator= ( AvlTree && other ) --> Big Five Move *assignment* operator // void printLevelOrder( ) --> Print tree in LEVEL order :-) // ******************ERRORS******************************** // Throws UnderflowException as warranted template <typename Comparable> class AvlTree { public: /** * Basic constructor for an empty tree */ AvlTree( ) : root( NULL ) { //cout << " [d] AvlTree constructor called. " << endl; } /** * Vector of data initializer (needed for move= operator rvalue) */ AvlTree( vector<Comparable> vals ) : root( NULL ) { insert(vals); } //******************************************************************************************* // START AVL TREES PART II - TODO: Implement // Other functions to look for include: clone, makeEmpty, printLevelOrder /** * Destroy contents of the AvlTree object - Big Five Destructor */ ~AvlTree( ) { //cout << " [d] AvlTree Destructor called. " << endl; // Empty out the AVL Tree and destroy all nodes (makeEmpty?) } /** * Copy other to new object - Big Five Copy Constructor */ AvlTree( const AvlTree &other ) : root( NULL ) { cout << " [d] Copy Constructor Called." << endl; // Copy contents of other to ourselves (maybe clone?) // Get a deep copy of other's tree } /* ...

C++Write a method Node Nodereverse() which reverses a list..pdfarjunenterprises1978

C++ Write a method Node *Node::reverse() which reverses a list. Solution #include #include /* Link list node */ struct node { int data; struct node* next; }; /* Function to reverse the linked list */ static void reverse(struct node** head_ref) { struct node* prev = NULL; struct node* current = *head_ref; struct node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; } /* Function to push a node */ void push(struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print linked list */ void printList(struct node *head) { struct node *temp = head; while(temp != NULL) { printf(\"%d \", temp->data); temp = temp->next; } } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 85); printf(\"Given linked list\ \"); printList(head); reverse(&head); printf(\"\ Reversed Linked list \ \"); printList(head); getchar(); }.

Implement of c & its coding programming by sarmad balochSarmad Baloch

C++ adt c++ implementationsRex Mwamba

This document provides code examples for implementing common data structures in C++. It includes code for implementing a binary search tree with functions for insertion, removal, and traversal. It also includes code for implementing stacks, queues, and trees as abstract data types with functions for common operations like push, pop, enqueue, dequeue, and traversal. The code demonstrates how to create node structures to represent data elements and link them together to form the desired data structures.

This is a c++ binary search program I worked so far but still cant g.pdfkostikjaylonshaewe47

This is a c++ binary search program I worked so far but still cant get it right. Can anyone help me? Big thanks!! the client should not be modified /* *File: client.cpp *Author: Yingwu Zhu *Warning: do not change this file and use it as is. *Last Modififcation: 10/21/2016 */ #include #include #include #include #include #include \"bst.h\" using namespace std; int main(int argc, char* argv[]) { if (argc != 2) { cout << \"Format: \" << argv[0] << \" [data file]\" << endl; return 0; } ifstream fin(argv[1]); int cases; fin >> cases; int passed = 0; for (int i = 1; i <= cases; i++) { cout << \"Checking test case #\" << i << \" ... \"; BST T; set S; int n, x; fin >> n; bool ok = true; vector tmp; int rem = 0; for (int j = 0; j < n; j++) { fin >> x; T.Insert(x); S.insert(x); ok &= (T.Search(x) && T.RecurSearch(x)); if (tmp.empty()) tmp.push_back(x); if (rand()%10 < 3) { T.Erase(tmp[0]); S.erase(tmp[0]); ok &= (T.Search(tmp[0]) == false); tmp.pop_back(); rem++; } } if (rem ok &= (T.MaxElement() == *S.rbegin()); while (!S.empty() && !T.Empty()) { int x = T.MinElement(); ok &= (x == *S.begin()); T.Erase(x); S.erase(S.begin()); } cout << (ok ? \"Passed!\" : \"Failed\") << endl; passed += ok; } cout << passed << \" of \" << cases << \" test cases have passed!\ \"; if (passed == cases) cout << endl << \"Congratulations! Good to Submit Your Code\ \"; else if ((double)passed/cases >= 0.95) cout << endl << \"You are almost there, but need to fix some bugs.\ \"; else cout << endl << \"Your code needs a lot of fixes for submission\ \"; return 0; } ===================================================================== ======= //bst.h #ifndef _BST_H_ #define _BST_H_ #include using namespace std; class BST { private: class Node { public: int data; Node* left; Node* right; }; Node* root; //root node pointer //you may add your auxiliary functions here! public: BST(); //constructor ~BST(); //destructor bool Empty() const; void Insert(int val); int MinElement() const; int MaxElement() const; bool Search(int val) const; bool RecurSearch(int val) const; void Erase(int val); }; #endif ===================================================================== ======= /* bst.cpp Subject: Binary Seach Tree Modification Time:10/26/2016 */ #include #include\"bst.h\" using namespace std; BST::BST(){ root= NULL; } BST::~BST(){ delete root; delete root->left; delete root->right; } bool BST::Empty() const { return data; } void BST::Insert(int val){ Node* p= new Node; p->data= val; Node* cur = root; if(val < cur->data){ cur = cur -> left; } else{ right->next=val; } } int BST::MinElement() const { Node* cur; while(cur->left != NULL){ cur = cur->left; } return(cur->data); } int BST::MaxElement() const{ if(root==NULL){ return 0; } if(root->left>root->data){ root->data=root->right; } else if(root->right>root->data){ root->data=root->right; } return root->data; } bool BST:: Search(int val) const{ Node* cur; cur = root; while(cur!=NULL){ if(cur->data == val){ return true; } else if(cur->data .

DATASTRUCTURES PPTS PREPARED BY M V BRAHMANANDA REDDYMalikireddy Bramhananda Reddy

This document discusses binary search trees and provides source code to implement binary search tree traversal operations. It explains that a binary search tree is a binary tree where the left child of a node is less than the parent and the right child is greater. It provides code for preorder, inorder, and postorder traversals of the binary search tree and outputs the traversal order for a sample tree.

DS Code (CWH).docxKamalSaini561034

The document discusses various operations on linked lists and arrays in C language like creation, traversal, insertion, deletion etc. It includes code snippets to implement array as an abstract data type, linear and binary search on arrays, creation and traversal of singly linked lists, different ways to insert and delete nodes from linked lists, operations on circular linked lists and basics of doubly linked lists.

Please read the comment ins codeExpressionTree.java-------------.pdfshanki7

Please read the comment ins code ExpressionTree.java ---------------------------------- /** * This is the class for Expression Tree. * Used to create Expression Tree and Evaluate it */ /** * Following logic is used to construct a Tree * Here we use stack for Preparing Tree * Loop through given Expression String * If Character is Operand , Create node and push to stack * If Character is Operator then * 1)Create Node for Operator * 2)Pop 2 nodes from Stack and Made * OpretorNode--> left == first node pop * OpretorNode--> right == second node pop * At the end of creation of Expression Tree, Stack have only one node , which is root of Expression tree */ /** Class ExpressionTree **/ class ExpressionTree { /** class TreeNode * Stored Character ==> Digit(0..9) or a Operator +,-,*,/ * Left Node and Right Node * * **/ class TreeNode { char data; TreeNode left, right; /** constructor **/ public TreeNode(char data) { this.data = data; this.left = null; this.right = null; } } /** class StackNode **/ class StackNode { TreeNode treeNode; StackNode next; /** constructor **/ public StackNode(TreeNode treeNode) { this.treeNode = treeNode; next = null; } } private static StackNode top; /** constructor * Constructor takes input string like \"+-+7*935*82*625\" * Input should be in Prefix notation * **/ public ExpressionTree(String expression) { top = null; //Call Method for prepare expression tree buildTree(expression); } /** function to clear tree **/ public void clear() { top = null; } /** function to push a node **/ private void push(TreeNode ptr) { if (top == null) top = new StackNode(ptr); else { StackNode nptr = new StackNode(ptr); nptr.next = top; top = nptr; } } /** function to pop a node * When it find operator pop 2 elements from Stack * * **/ private TreeNode pop() { if (top == null) throw new RuntimeException(\"Underflow\"); else { TreeNode ptr = top.treeNode; top = top.next; return ptr; } } /** function to get top node **/ private TreeNode peek() { return top.treeNode; } /** function to insert character **/ private void insert(char val) { try { //If Operand , Create node and push to Stack if (isDigit(val)) { TreeNode nptr = new TreeNode(val); push(nptr); } //If Operator , Create node and popup 2 elements and make them its right and left else if (isOperator(val)) { TreeNode nptr = new TreeNode(val); nptr.left = pop(); nptr.right = pop(); push(nptr); } } catch (Exception e) { System.out.println(\"Invalid Expression\"); } } /** function to check if digit **/ private boolean isDigit(char ch) { return ch >= \'0\' && ch <= \'9\'; } /** function to check if operator **/ private boolean isOperator(char ch) { return ch == \'+\' || ch == \'-\' || ch == \'*\' || ch == \'/\'; } /** function to convert character to digit **/ private int toDigit(char ch) { return ch - \'0\'; } /** function to build tree from input */ public void buildTree(String eqn) { for (int i = eqn.length() - 1; i >= 0; i--) insert(eqn.charAt(i)); } /** function to evaluate tree */ public dou.

#includeiostream#includecstdio#includecstdlibusing names.pdfKUNALHARCHANDANI1

Data Structures in C++I am really new to C++, so links are really .pdfrohit219406

Data Structures in C++ I am really new to C++, so links are really hard topic for me. It would be nice if you can provide explanations of what doubly linked lists are and of some of you steps... Thank you In this assignment, you will implement a doubly-linked list class, together with some list operations. To make things easier, you’ll implement a list of int, rather than a template class. Solution A variable helps us to identify the data. For ex: int a = 5; Here 5 is identified through variable a. Now, if we have collection of integers, we need some representation to identify them. We call it array. For ex: int arr[5] This array is nothing but a Data Structure. So, a Data Structure is a way to group the data. There are many Data Structures available like Arrays, Linked List, Doubly-Linked list, Stack, Queue, etc. Doubly-Linked list are the ones where you can traverse from the current node both in left and right directions. Why so many different types of Data Structures are required ? Answer is very simple, grouping of data, storage of data and accessing the data is different. For example, in case of Arrays we store all the data in contiguous locations. What if we are not able to store the data in contiguous locations because we have huge data. Answer is go for Linked List/Doubly-Linked list. Here we can store the data anywhere and link the data through pointers. I will try to provide comments for the code you have given. May be this can help you. #pragma once /* dlist.h Doubly-linked lists of ints */ #include class dlist { public: dlist() { } // Here we are creating a NODE, it has a integer value and two pointers. // One pointer is to move to next node and other to go back to previous node. struct node { int value; node* next; node* prev; }; // To return head pointer, i.e. start of the Doubly-Linked list. node* head() const { return _head; } // To return Tail pointer, i.e. end of the Doubly-Linked list. node* tail() const { return _tail; } // **** Implement ALL the following methods **** // Returns the node at a particular index (0 is the head). node* at(int index){ int cnt = 0; struct node* tmp = head(); while(tmp!=NULL) { if (cnt+1 == index) return tmp; tmp = tmp->next; } } // Insert a new value, after an existing one void insert(node *previous, int value){ // check if the given previous is NULL if (previous == NULL) { printf(\"the given previous node cannot be NULL\"); return; } // allocate new node struct node* new_node =(struct node*) malloc(sizeof(struct node)); // put in the data new_node->data = new_data; // Make next of new node as next of previous new_node->next = previous->next; // Make the next of previous as new_node previous->next = new_node; // Make previous as previous of new_node new_node->prev = previous; // Change previous of new_node\'s next node if (new_node->next != NULL) new_node->next->prev = new_node; } // Delete the given node void del(node* which){ struct node* head_ref = head(); /* base case */ if(*head_ref == NUL.

#includeiostream #includecstdio #includecstdlib using na.pdfharihelectronicspune

#include #include #include using namespace std; struct node { int val; struct node *next; }*startNode; // declaring class class LinkedList { public: node* create_node(int); void insert_last(); void sort(); void search(); void reverse(); void display(); LinkedList() { startNode = NULL; } }; // main main() { int userChoice, linkedListNodes, i; LinkedList LinkList; startNode = NULL; while (1) { // displaying menu cout<<\" 1)Insert\"; cout<<\"2) Remove\"; cout<<\"3) Search\"; cout<<\"4) Display\"; cout<<\"5) Reverse\"; cout<<\"6) Exit \"; // reading user choice cout<<\"Enter your userChoice : \"; cin>>userChoice; switch(userChoice) { case 1: cout<<\"Inserting node to linked list: \"; LinkList.insert_begin(); cout; break; case 2: cout<<\"Delete element from linked list: \"; LinkList.delete(); break; case 3: cout<<\"Searching data in linked list: \"; LinkList.search(); cout; break; case 4: cout<<\"Displaying linked list data: \"; LinkList.display(); cout; break; case 5: cout<<\"Linked list reversing: \"; LinkList.reverse(); cout; break; case 6: cout<<\"Exiting...\"; exit(1); break; default: cout<<\"Enter correct userChoice\"; } } } // node creating to store into list node *LinkedList::create_node(int val) { struct node *tempNode, *tempNode; tempNode = new(struct node); if (tempNode == NULL) { cout<<\"No memory allocated \"; return 0; } else { tempNode->val = val; tempNode->next = NULL; return tempNode; } } /* * Inserting Node at last */ void LinkedList::insert_last() { int val; cout<<\"Enter the val to be inserted: \"; cin>>val; struct node *tempNode, *tempNode; tempNode = create_node(val); tempNode = startNode; while (tempNode->next != NULL) { tempNode = tempNode->next; } tempNode->next = NULL; tempNode->next = tempNode; cout<<\"Element Inserted\"; } // deleting element void LinkedList::delete() { int position, i, count = 0; if (startNode == NULL) { cout<<\"Linkedlist empty\"<>position; struct node *tempNode, *ptr; tempNode = startNode; if (position == 1) { startNode = tempNode->next; } else { while (tempNode != NULL) { tempNode = tempNode->next; count++; } if (position > 0 && position <= count) { tempNode = startNode; for (i = 1;i < position;i++) { ptr = tempNode; tempNode = tempNode->next; } ptr->next = tempNode->next; } else { cout<<\"Enter correct position\"; } } } // search data in linked list void LinkedList::search() { int val, position = 0; bool flagValue = false; if (startNode == NULL) { cout<<\"List is empty\"; return; } cout<<\"Enter the val to search: \"; cin>>val; struct node *tempNode; tempNode = startNode; while (tempNode != NULL) { position++; if (tempNode->val == val) { flagValue = true; cout<<\"Data \"<next; } if (!flagValue) cout<<\"data not found\"; } // linkedlist reverese void LinkedList::reverse() { struct node *pointer1, *pointer2, *pointer3; if (startNode == NULL) { cout<<\"List is empty\"<next == NULL) { return; } pointer1 = startNode; pointer2 = pointer1->next; pointer3 = pointer2->next; pointer1->next = NULL; pointer2->.

operating system linux,ubuntu,Mac#include iostream #include .pdfaquacareser

//operating system linux,ubuntu,Mac #include #include #include #include // for Time using namespace std; struct Node { int number; struct Node* nextNode; }; //append Method Implementation void append(struct Node** head, int num) { if (*head == NULL) { // checking if first node is NULL or not (*head) = (struct Node*)malloc(sizeof(struct Node)); (*head)->number = num; (*head)->nextNode = NULL; } else { struct Node* temp = *head; while (temp->nextNode != NULL) { temp = temp->nextNode; } struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); //dynamically allocation of memory newNode->number = num; newNode->nextNode = NULL; temp->nextNode = newNode; } } /* Getting Node with value from List*/ Node* search(struct Node** head, int value) { clock_t begin = clock(); std::cout<number == value) { clock_t end = clock(); std::cout<nextNode; } return NULL; } /*Display List Method Implementation*/ void printList(struct Node* head) { while (head != NULL) { std::cout << head->number << \" \"; head = head->nextNode; } std::cout << endl; } int main(int argc, char *argv[]) { struct Node* head = NULL,*temp; srand(time(0)); if ( argc != 3 ) // argc should be 2 for correct execution // We print error message std::cout<<\"Please Enter 3 argument\"< Solution //operating system linux,ubuntu,Mac #include #include #include #include // for Time using namespace std; struct Node { int number; struct Node* nextNode; }; //append Method Implementation void append(struct Node** head, int num) { if (*head == NULL) { // checking if first node is NULL or not (*head) = (struct Node*)malloc(sizeof(struct Node)); (*head)->number = num; (*head)->nextNode = NULL; } else { struct Node* temp = *head; while (temp->nextNode != NULL) { temp = temp->nextNode; } struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); //dynamically allocation of memory newNode->number = num; newNode->nextNode = NULL; temp->nextNode = newNode; } } /* Getting Node with value from List*/ Node* search(struct Node** head, int value) { clock_t begin = clock(); std::cout<number == value) { clock_t end = clock(); std::cout<nextNode; } return NULL; } /*Display List Method Implementation*/ void printList(struct Node* head) { while (head != NULL) { std::cout << head->number << \" \"; head = head->nextNode; } std::cout << endl; } int main(int argc, char *argv[]) { struct Node* head = NULL,*temp; srand(time(0)); if ( argc != 3 ) // argc should be 2 for correct execution // We print error message std::cout<<\"Please Enter 3 argument\"<.

Lab Week 2 Game Programming.docxteyaj1

This program implements a doubly linked list to print the list forward and backward. It defines a Node struct with data, next and prev pointers. It inserts nodes at the head of the list using InsertAtHead() and prints the list forward using Print() and backward using ReversePrint(). It initially inserts two nodes and prints the list both ways. It then inserts three more nodes at the head and prints the list again forward and backward.

Please help write BinaryTree-java Thank you! Create a class BinaryTr.pdfinfo750646

Please help write BinaryTree.java Thank you! Create a class BinaryTree. A class that implements the ADT binary tree. import java.util.Iterator; import java.util.NoSuchElementException; import StackAndQueuePackage.*; public class BinaryTree <T> implements BinaryTreeInterface<T> { private BinaryNode<T> root; public BinaryTree() { root = null; } // end default constructor public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); } // end constructor public BinaryTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor public void setTree(T rootData) { root = new BinaryNode<>(rootData); } // end setTree public void setTree(T rootData, BinaryTreeInterface<T> leftTree, BinaryTreeInterface<T> rightTree) { privateSetTree(rootData, (BinaryTree<T>)leftTree, (BinaryTree<T>)rightTree); } // end setTree private void privateSetTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree) { root = new BinaryNode<>(rootData); if ((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if ((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) root.setRightChild(rightTree.root); else root.setRightChild(rightTree.root.copy()); } // end if if ((leftTree != null) && (leftTree != this)) leftTree.clear(); if ((rightTree != null) && (rightTree != this)) rightTree.clear(); } // end privateSetTree //... private class PreorderIterator implements Iterator<T> { private StackInterface<BinaryNode<T>> nodeStack; public PreorderIterator() { nodeStack = new LinkedStack<>(); if (root != null) nodeStack.push(root); } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty(); } // end hasNext public T next() { BinaryNode<T> nextNode; if (hasNext()) { nextNode = nodeStack.pop(); BinaryNode<T> leftChild = nextNode.getLeftChild(); BinaryNode<T> rightChild = nextNode.getRightChild(); // Push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); } else { throw new NoSuchElementException(); } return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end PreorderIterator public void iterativePreorderTraverse () { StackInterface<BinaryNode<T>> nodeStack = new LinkedStack<>(); if (root != null) nodeStack.push(root); BinaryNode<T> nextNode; while (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); BinaryNode<T> leftChild = nextNode.getLeftChild(); BinaryNode<T> rightChild = nextNode.getRightChild(); // Push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); System.out.print(nextNode.getData() + " "); } // end while } // end iterativePreorderTraverse private class InorderIterator implements Iterator<T> { private StackInterface<BinaryNode<T>> nodeStack; private BinaryNode<T> cu.

MAINCPP include ltiostreamgt include ltstringgt u.pdfadityastores21

MAIN.CPP #include <iostream> #include <string> using namespace std; #include "bstree.h" // Prints a single string, used by FSTree::inorder to print all // values in the tree in correct order. void print_string (string s) { cout << s << endl; } // Prints a single string preceeded by a number of hyphens, used by // BSTree::preorder to print a visual representation of the tree. void print_string_depth (string s, int n) { for (int i = 0; i < n; i++) cout << '-'; cout << s << endl; } int main () { // Create a binary search tree. BSTree<string> t; // Insert some strings for testing. t.insert("dog"); t.insert("bird"); t.insert("cat"); t.insert("turtle"); t.insert("giraffe"); t.insert("snake"); t.insert("deer"); t.insert("groundhog"); t.insert("horse"); // Output the values stored in the tree. cout << "Values stored in the tree are:n"; t.inorder(print_string); cout << "n"; cout << "The structure of the tree is as follows:n"; t.preorder(print_string_depth); cout << "n"; } BSTREE.h #pragma once // A Binary Search Tree implementation. template <typename T> class BSTree { private: // A node in the tree. Each node has pointers to its left and right nodes // as well as its parent. When a node is created, the parent and data item // must be provided. class node { public: T data; node* left; node* right; node* parent; node (const T& d, node* p) { parent = p; data = d; left = right = nullptr; } }; // Pointer to the root node. Initially this is null for an empty tree. node* root; // Copy the subtree of another BSTree object into this object. Used by // the copy constructor and assignment operator. void copy (node* p) { if (p) { // If p points to a node... insert(p->data); // Insert data item copy(p->left); // Copy the left subtree copy(p->right); // Copy the right subtree } } // Destroy a node and all nodes in both subtrees. Called by the // destructor. void destroy (node* p) { if (p) { // If p is not null... destroy(p->left); // Destroy the left subtree destroy(p->right); // Destroy the right subtree delete p; // Destroy the node } } // Helper function to determine if a data value is contained in the tree. // Takes the data value being searched and a pointer to the node in the // tree. Returns pointer to node in which data item is found, a null // pointer otherwise. node* find (const T& d, node* p) const { // Given: p is a pointer to an existing node if (d == p->data) // Is this the value we're looking for? return p; if (d < p->data) // Check left side, if null then not found return p->left ? find(d, p->left) : nullptr; return p->right ? find(d, p->right) : nullptr; // Check right side... } // Helper function to insert a data item into the tree. Takes the data // and a pointer to a node in the tree. Recursively decends down the tree // until position were insertion should take place is found. void insert (const T& d, node* p) { // Given: p is a pointer to an existing node (root of a subtree) if (d < p->data) { // Insert into left subtree? if (p->left) // Left.

How to delete one specific node in linked list in CThanksSolu.pdffootstatus

How to delete one specific node in linked list in C? Thanks Solution #include #include struct node { int data; struct node *next; }; void deleteNode(struct node *head, struct node *n) { if(head == n) { if(head->next == NULL) { printf(\"There is only one node. The list can\'t be made empty \"); return; } head->data = head->next->data; n = head->next; head->next = head->next->next; free(n); return; } struct node *prev = head; while(prev->next != NULL && prev->next != n) prev = prev->next; if(prev->next == NULL) { printf(\"\ Given node is not present in Linked List\"); return; } prev->next = prev->next->next; free(n); return; } void push(struct node **head_ref, int new_data) { struct node *new_node = (struct node *)malloc(sizeof(struct node)); new_node->data = new_data; new_node->next = *head_ref; *head_ref = new_node; } void printList(struct node *head) { while(head!=NULL) { printf(\"%d \",head->data); head=head->next; } printf(\"\ \"); } int main() { struct node *head = NULL; push(&head,3); push(&head,2); push(&head,6); push(&head,5); push(&head,11); push(&head,10); push(&head,15); push(&head,12); printf(\"Given Linked List: \"); printList(head); printf(\"\ Deleting node %d: \", head->next->next->data); deleteNode(head, head->next->next); printf(\"\ Modified Linked List: \"); printList(head); printf(\"\ Deleting first node \"); deleteNode(head, head); printf(\"\ Modified Linked List: \"); printList(head); getchar(); return 0; }.

Ds 2 cycleChaitanya Kn

The document discusses the implementation of a binary search tree (BST) using both recursive and non-recursive traversal methods. It defines a BST node structure with left and right child pointers. Functions are included to insert nodes, perform inorder, preorder and postorder traversals recursively and non-recursively using stacks. Main inserts sample nodes into the tree and calls the various traversal functions to output the node values in the specified orders.

A)B) C++ program to create a Complete Binary tree from its Lin.pdfanton291

A) B) // C++ program to create a Complete Binary tree from its Linked List // Representation #include #include #include using namespace std; // Linked list node struct ListNode { int data; ListNode* next; }; // Binary tree node structure struct BinaryTreeNode { int data; BinaryTreeNode *left, *right; }; // Function to insert a node at the beginning of the Linked List void push(struct ListNode** head_ref, int new_data) { // allocate node and assign data struct ListNode* new_node = new ListNode; new_node->data = new_data; // link the old list off the new node new_node->next = (*head_ref); // move the head to point to the new node (*head_ref) = new_node; } // method to create a new binary tree node from the given data BinaryTreeNode* newBinaryTreeNode(int data) { BinaryTreeNode *temp = new BinaryTreeNode; temp->data = data; temp->left = temp->right = NULL; return temp; } // converts a given linked list representing a complete binary tree into the // linked representation of binary tree. void convertList2Binary(ListNode *head, BinaryTreeNode* &root) { // queue to store the parent nodes queue q; // Base Case if (head == NULL) { root = NULL; // Note that root is passed by reference return; } // 1.) The first node is always the root node, and add it to the queue root = newBinaryTreeNode(head->data); q.push(root); // advance the pointer to the next node head = head->next; // until the end of linked list is reached, do the following steps while (head) { // 2.a) take the parent node from the q and remove it from q BinaryTreeNode* parent = q.front(); q.pop(); // 2.c) take next two nodes from the linked list. We will add // them as children of the current parent node in step 2.b. Push them // into the queue so that they will be parents to the future nodes BinaryTreeNode *leftChild = NULL, *rightChild = NULL; leftChild = newBinaryTreeNode(head->data); q.push(leftChild); head = head->next; if (head) { rightChild = newBinaryTreeNode(head->data); q.push(rightChild); head = head->next; } // 2.b) assign the left and right children of parent parent->left = leftChild; parent->right = rightChild; } } // Utility function to traverse the binary tree after conversion void inorderTraversal(BinaryTreeNode* root) { if (root) { inorderTraversal( root->left ); cout << root->data << \" \"; inorderTraversal( root->right ); } } // Driver program to test above functions int main() { // create a linked list shown in above diagram struct ListNode* head = NULL; push(&head, 36); /* Last node of Linked List */ push(&head, 30); push(&head, 25); push(&head, 15); push(&head, 12); push(&head, 10); /* First node of Linked List */ BinaryTreeNode *root; convertList2Binary(head, root); cout << \"Inorder Traversal of the constructed Binary Tree is: \ \"; inorderTraversal(root); return 0; } c) #include #include using namespace std; template class bintree { bintree *left; T data; bintree *right; public : bintree() { left=right=NULL; } void create(); void preorder(); void inorder(); void pos.

1. Add a breadth-first (level-order) traversal function to the binar.pdfarjuncp10

1. Add a breadth-first (level-order) traversal function to the binary tree code. 2. Add a function to find the height of a tree. 3. Re-implement one of the depth-first traversal methods using a stack instead of recursion. 4. Add a link to each nodes parent node. #include #include #include using namespace std; template < typename T > class TreeNode { public: T element; // TreeNode < T > * left; // TreeNode < T > * right; // TreeNode * next; TreeNode() // { left = NULL; next = NULL; } TreeNode(T element) // Constructor { this->element = element; left = NULL; right = NULL; } }; template < typename T > class BinaryTree { public: BinaryTree(); BinaryTree(T elements[], int arraySize); bool insert(T element); void inorder(); void preorder(); void postorder(); int getSize(); bool search(T element); void breadthFirstTraversal(); int depth(); private: TreeNode < T > * root; int size; void inorder(TreeNode < T > * root); void postorder(TreeNode < T > * root); void preorder(TreeNode < T > * root); bool search(T element, TreeNode < T > * root); int depth(TreeNode * root); }; template < typename T > BinaryTree < T >::BinaryTree() { root = NULL; size = 0; } template < typename T > BinaryTree < T >::BinaryTree(T elements[], int arraySize) { root = NULL; size = 0; for (int i = 0; i < arraySize; i++) { insert(elements[i]); } } template < typename T > bool BinaryTree < T >::insert(T element) { if (root == NULL) root = new TreeNode < T > (element); // Create a new root else { // Locate the parent node TreeNode < T > * parent = NULL; TreeNode < T > * current = root; while (current != NULL) if (element < current->element) { parent = current; current = current->left; } else if (element > current->element) { parent = current; current = current->right; } else return false; // Duplicate node not inserted // Create the new node and attach it to the parent node if (element < parent->element) parent->left = new TreeNode < T > (element); else parent->right = new TreeNode < T > (element); } size++; return true; // Element inserted } /* Inorder traversal */ template < typename T > void BinaryTree < T >::inorder() { inorder(root); } /* Inorder traversal from a subtree */ template < typename T > void BinaryTree < T >::inorder(TreeNode < T > * root) { if (root == NULL) return; inorder(root->left); cout << root->element << \" \"; inorder(root->right); } /* Postorder traversal */ template < typename T > void BinaryTree < T >::postorder() { postorder(root); } /** Inorder traversal from a subtree */ template < typename T > void BinaryTree < T >::postorder(TreeNode < T > * root) { if (root == NULL) return; postorder(root->left); postorder(root->right); cout << root->element << \" \"; } /* */ template < typename T > void BinaryTree < T >::preorder() { preorder(root); } /* */ template < typename T > void BinaryTree < T >::preorder(TreeNode < T > * root) { if (root == NULL) return; cout << root->element << \" \"; preorder(root->left); preorder(root->right); } /**/ template < typename .

Myasthenia gravis (Neuromuscular disorder)Mohamed Rizk Khodair

Drugs in Anaesthesia and Intensive Care,.pdfcrewot855

Binary Tree in C++ coding in the data structure

1. // Binary Tree in C++ #include <stdlib.h> #include <iostream> using namespace std; struct node { int data; struct node *left; struct node *right; }; // New node creation struct node *newNode(int data) { struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Traverse Preorder void traversePreOrder(struct node *temp) { if (temp != NULL) { cout << " " << temp->data; traversePreOrder(temp->left); traversePreOrder(temp->right); } } // Traverse Inorder void traverseInOrder(struct node *temp) { if (temp != NULL) { traverseInOrder(temp->left); cout << " " << temp->data; traverseInOrder(temp->right); } } // Traverse Postorder void traversePostOrder(struct node *temp) { if (temp != NULL) {

2. traversePostOrder(temp->left); traversePostOrder(temp->right); cout << " " << temp->data; } } int main() { struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout << "preorder traversal: "; traversePreOrder(root); cout << "nInorder traversal: "; traverseInOrder(root); cout << "nPostorder traversal: "; traversePostOrder(root); } // Binary Search Tree operations in C++ #include <iostream> using namespace std; struct node { int key; struct node *left, *right; }; // Create a node struct node *newNode(int item) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Inorder Traversal void inorder(struct node *root) { if (root != NULL) { // Traverse left inorder(root->left);

3. // Traverse root cout << root->key << " -> "; // Traverse right inorder(root->right); } } // Insert a node struct node *insert(struct node *node, int key) { // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; } // Find the inorder successor struct node *minValueNode(struct node *node) { struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; } // Deleting a node struct node *deleteNode(struct node *root, int key) { // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { // If the node is with only one child or no child if (root->left == NULL) {

4. struct node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node *temp = root->left; free(root); return temp; } // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } return root; } // Driver code int main() { struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "nAfter deleting 10n"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); }

Binary Tree in C++ coding in the data structure

Recommended

More Related Content

Similar to Binary Tree in C++ coding in the data structure (20)

Recently uploaded (20)

Binary Tree in C++ coding in the data structure