Data Structures (5050) Records (Struct) PDF

Data Structures (5050) Records (Struct) Dr. Zein Salah College of IT and CE Palestine Polytechnic University  Records A record is a structured data type made up of a finite collection of not necessarily homogeneous elements, called ‘fields...

Data Structures (5050) Records (Struct) Dr. Zein Salah College of IT and CE Palestine Polytechnic University  Records A record is a structured data type made up of a finite collection of not necessarily homogeneous elements, called ‘fields’. Records (Struct) Logical Level: SNo SName SBirthDate Student Record (int) (string) (date) Fields are used as part selectors Fields Data Structures, Salah&Tamimi, 2022  Records Physical Level: Records (Struct) SNo A record is stored in a contiguous block of memory. SNo SName SBirthDate Student Record (int) (string) (date) SName 2 Bytes 20 Bytes 6 Bytes To access individual fields, an offset table stores, for each field, the offset from the base address. SBirthDate Data Structures, Salah&Tamimi, 2022  Records SNo SName SBirthDate Student Record (int) (string) (date) Records (Struct) SNo 2 Bytes 20 Bytes 6 Bytes To access individual fields, an offset table stores, for each field, the offset from the base address. SName Field SNo SName SBirthDate Offset 0 2 22 EA(field) = BA + offset SBirthDate E.g., Assume the BA = 1000, then EA(SNo) = 1000, EA(SName) = 1002, and EA(SBirthDate) = 1022 Data Structures, Salah&Tamimi, 2022  Struct (records in C/C++) Defining a struct: Records (Struct) void main() struct Std_Rec { { struct int SNo; { char SName; int SNo; }; char SName; } s1; void main() cin >> s1.SNo; { cin >> s1.SName; Std_Rec s1; system("PAUSE"); cin >> s1.SNo; } cin >> s1.SName; system("PAUSE"); } Simple way, but bad, not practical! Better way Data Structures, Salah&Tamimi, 2022  Struct (records in C/C++) Data Type Defining a struct Records (Struct) void main() struct Std_Rec { { struct int SNo; { char SName; int SNo; }; char SName; } s1; void main() cin >> s1.SNo; { cin >> s1.SName; Std_Rec s1; system("PAUSE"); cin >> s1.SNo; } cin >> s1.SName; system("PAUSE"); } Simple way, but bad, not practical! Better way Data Structures, Salah&Tamimi, 2022  Struct (records in C/C++) Now, we will learn: Records (Struct) Struct I/O Nested Struct Initialization, assignment, and comparison Array inside struct Array of struct Passing struct as parameter Struct as function return value Pointers to struct (later) Data Structures, Salah&Tamimi, 2022  Struct (records in C/C++) struct Std_Rec Struct I/O { int SNo; Records (Struct) Struct cannot be read/written }; char SName; as a whole. void main() Instead, we read/write { Std_Rec s1; individual fields cin >> s1; X cin >> s1.SNo;  cin >> s1.SName;  cout s1.SName; cin >> s1.SBirthDate.dd >> s1.SBirthDate.mm >> s1.SBirthDate.yy; cout > s1.SNo; { cin >> s1.SName; cinmm, int dd, >> yy; s1.SBirthDate.dd >> s1.SBirthDate.mm >> } SBirthDate; s1.SBirthDate.yy; }; cout next = NULL; if (m_Head == NULL) Special Case ! m_Head = x; else { NodePTR t = m_Head; while (t->next != NULL) t = t->next; t->next = x; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head insertIntoSortedList 5 9 17.... 98 Linked Lists We want to insert the new node into x 14 the correct position Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head insertIntoSortedList 5 9 17.... 98 void SinglyLinkedList::insertIntoSortedList(int val) { Linked Lists NodePTR x = new Node; x->value = val; if (m_Head == NULL || val value) // add before head { x->next = m_Head; m_Head = x; } else // insert at the correct position after head { NodePTR t = m_Head; while ((t->next != NULL) && (t->next->value next; x->next = t->next; t->next = x; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head insertIntoSortedList 5 9 17.... 98 x Linked Lists 2 Case 1: Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head insertIntoSortedList 5 9 17.... 98 x Linked Lists 2 Case 1: void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val; if (m_Head == NULL || val value) // add before head { x->next = m_Head; m_Head = x; } else // insert at the correct position after head...... Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head insertIntoSortedList 5 9 17.... 98 x Linked Lists 2 Case 1: void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val; if (m_Head == NULL || val value) // add before head { x->next = m_Head; m_Head = x; } else // insert at the correct position after head...... Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT insertIntoSortedList 5 9 17.... 98 m_Head Linked Lists 2 Case 1: x void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val; if (m_Head == NULL || val value) // add before head { x->next = m_Head; m_Head = x; } else // insert at the correct position after head...... Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head insertIntoSortedList 5 9 17.... 98 x Linked Lists 13 Case 2: void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val;...... else // insert at the correct position after head { NodePTR t = m_Head; while ((t->next != NULL) && (t->next->value next; x->next = t->next; t->next = x; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head t insertIntoSortedList 5 9 17.... 98 x Linked Lists 13 Case 2: void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val;...... else // insert at the correct position after head { NodePTR t = m_Head; while ((t->next != NULL) && (t->next->value next; x->next = t->next; t->next = x; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head t insertIntoSortedList 5 9 17.... 98 Linked Lists 13 Case 2: x void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val;...... else // insert at the correct position after head { NodePTR t = m_Head; while ((t->next != NULL) && (t->next->value next; x->next = t->next; t->next = x; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head t insertIntoSortedList 5 9 17.... 98 x Linked Lists Case 2: 133 void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val;...... else // insert at the correct position after head { NodePTR t = m_Head; while ((t->next != NULL) && (t->next->value next; x->next = t->next; t->next = x; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT m_Head t insertIntoSortedList 5 9 17.... 98 Linked Lists Case 2: x 133 void SinglyLinkedList::insertIntoSortedList(int val) { NodePTR x = new Node; x->value = val;...... else // insert at the correct position after head { NodePTR t = m_Head; while ((t->next != NULL) && (t->next->value next; x->next = t->next; t->next = x; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT main() void main() { Linked Lists SinglyLinkedList list; list.addAtBeginning(5); list.addAtBeginning(8);... list.addAtEnd(15);... list.printOut(); cout val; while (val != 0) { if (sorted) insertIntoSortedList(val); else addAtEnd(val); cin >> val; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT class SinglyLinkedList readAndCreate { public: void addAtBeginning(int n); void addAtEnd(int n); Linked Lists void readAndCreate( bool sorted = false ); void insertIntoSortedList(int n); void SinglyLinkedList::readAndCreate(bool sorted)... { }; int val; cin >> val; while (val != 0) Default Parameter { if (sorted) insertIntoSortedList(val); else addAtEnd(val); cin >> val; } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT class SinglyLinkedList readAndCreate { public: void addAtBeginning(int n); void addAtEnd(int n); Linked Lists void readAndCreate( bool sorted = false ); void insertIntoSortedList(int n); void SinglyLinkedList::readAndCreate(bool sorted)... { }; int val; void main() { cin >> val; SinglyLinkedList list2; while (val != 0) { list2.readAndCreate(true); if (sorted) insertIntoSortedList(val); list2.readAndCreate(false); else list2.readAndCreate(); addAtEnd(val); cin >> val;... } } } Data Structures, Salah&Tamimi, 2022  Singly-Linked List ADT class SinglyLinkedList readAndCreate { public: void addAtBeginning(int n); void addAtEnd(int n); Linked Lists void readAndCreate( bool sorted = false ); void insertIntoSortedList(int n); void SinglyLinkedList::readAndCreate(bool sorted)... { }; int val; void main() { cin >> val; SinglyLinkedList list2; while (val != 0) { list2.readAndCreate(true); if (sorted) insertIntoSortedList(val); list2.readAndCreate(false); else list2.readAndCreate(); addAtEnd(val); cin >> val;... } Equivalent } } Data Structures, Salah&Tamimi, 2022  The End Thank you ! Linked Lists Data Structures, Salah&Tamimi, 2022 Data Structures (5050) Linked Lists (Part 3) Dr. Zein Salah College of IT and CE Palestine Polytechnic University  Preview Previous lecture: Singly-Linked List head Linked Lists..... Today: Doubly-Linked List head..... Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Basic building block is called a node. A Doubly-linked list (DLL) consists of a sequence of nodes. Linked Lists Each node has two parts: - Data part (single or multiple values) - Pointer that points to another node, and - a pointer that points to the previous node Data Part Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Defining a node: again, we use a struct struct Node Linked Lists { int value; // or num, data, etc. Node *next, *prev; } typedef Node* NodePTR; prev next value Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 q Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 t t->next = p->next; t->prev = p; Rule: Connect then disconnect Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 t t->next = p->next; t->prev = p; Rule: Connect then disconnect p->next->prev = t; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 t t->next = p->next; t->prev = p; Rule: Connect then disconnect p->next->prev = t; p->next = t; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node We want to remove this node a Linked Lists 10 20 Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node a t Linked Lists 10 20 Node *t = a->next; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node a t Linked Lists 10 20 Node *t = a->next; a->next = a->next->next; t->next-prev = a; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node a t Linked Lists 10 20 Node *t = a->next; a->next = a->next->next; t->next-prev = a; delete t; Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example Examples: Count the number of nodes of a DLL: same as with SLL Linked Lists Print the values stored in the nodes: same as with SLL Q: How can we print nodes’ values backward? head..... Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; Q: Why must we else { do this check? NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists ADT class DoublyLinkedList { public: DoublyLinkedList(); ~DoublyLinkedList(); Linked Lists void addAtBeginning(int n); void addAtEnd(int n); void insertIntoSortedList(int n); void readAndCreate(bool sorted = false); void printOut(); bool isSorted(); int getSize(); private: struct Node { The rest …. int value; Node *next, *prev; }; typedef Node *NodePTR; NodePTR m_Head; }; Data Structures, Salah&Tamimi, 2022  Circular Linked Lists Circular SLL: head Linked Lists..... Circular DLL: head..... Data Structures, Salah&Tamimi, 2022  Circular Linked Lists Circular SLL, Circular DLL: Think how to implement functions like: addAtBeginning, addAtEnd, Linked Lists getSize, printList, etc. head.... head.... Data Structures, Salah&Tamimi, 2022  The End Thank you ! Linked Lists Data Structures, Salah&Tamimi, 2022 Data Structures (5050) Linked Lists (Part 3) Dr. Zein Salah College of IT and CE Palestine Polytechnic University  Preview Previous lecture: Singly-Linked List head Linked Lists..... Today: Doubly-Linked List head..... Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Basic building block is called a node. A Doubly-linked list (DLL) consists of a sequence of nodes. Linked Lists Each node has two parts: - Data part (single or multiple values) - Pointer that points to another node, and - a pointer that points to the previous node Data Part Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Defining a node: again, we use a struct struct Node Linked Lists { int value; // or num, data, etc. Node *next, *prev; } typedef Node* NodePTR; prev next value Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 q Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 t t->next = p->next; t->prev = p; Rule: Connect then disconnect Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 t t->next = p->next; t->prev = p; Rule: Connect then disconnect p->next->prev = t; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Insert a node between two linked nodes p Linked Lists 10 20 30 t t->next = p->next; t->prev = p; Rule: Connect then disconnect p->next->prev = t; p->next = t; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node We want to remove this node a Linked Lists 10 20 Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node a t Linked Lists 10 20 Node *t = a->next; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node a t Linked Lists 10 20 Node *t = a->next; a->next = a->next->next; t->next-prev = a; Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists Delete a node a t Linked Lists 10 20 Node *t = a->next; a->next = a->next->next; t->next-prev = a; delete t; Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example Examples: Count the number of nodes of a DLL: same as with SLL Linked Lists Print the values stored in the nodes: same as with SLL Q: How can we print nodes’ values backward? head..... Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; else { NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked List Example: Concatenate a x..... b... Linked Lists void concatenateDLL(NodePTR a, NodePTR b) { if (a == NULL) a = b; Q: Why must we else { do this check? NodePTR x = a; while (x->next != NULL) x = x->next; x->next = b; if (b != NULL) b->prev = x; } } Data Structures, Salah&Tamimi, 2022  Doubly-Linked Lists ADT class DoublyLinkedList { public: DoublyLinkedList(); ~DoublyLinkedList(); Linked Lists void addAtBeginning(int n); void addAtEnd(int n); void insertIntoSortedList(int n); void readAndCreate(bool sorted = false); void printOut(); bool isSorted(); int getSize(); private: struct Node { The rest …. int value; Node *next, *prev; }; typedef Node *NodePTR; NodePTR m_Head; }; Data Structures, Salah&Tamimi, 2022  Circular Linked Lists Circular SLL: head Linked Lists..... Circular DLL: head..... Data Structures, Salah&Tamimi, 2022  Circular Linked Lists Circular SLL, Circular DLL: Think how to implement functions like: addAtBeginning, addAtEnd, Linked Lists getSize, printList, etc. head.... head.... Data Structures, Salah&Tamimi, 2022  The End Thank you ! Linked Lists Data Structures, Salah&Tamimi, 2022 Data Structures (5050) Templates Dr. Zein Salah College of IT and CE Palestine Polytechnic University  Problem Think about the implementation of the max function ! int max(int x, int y); Templates float max(float x, float y);... All these functions have the form type max(type x, type y) { if (x >= y) return x; else return y; } Data Structures, Salah&Tamimi, 2022  Function Templates Idea: We usually pass variables as template parameters to functions, likewise, Type max(Type x, Type y) we pass types as parameters { if (x >= y) to templates. Templates return x; else return y; } Data Structures, Salah&Tamimi, 2022  Function Templates Idea: We usually pass variables as template parameters to functions, likewise, Type max(Type x, Type y) we pass types as parameters { if (x >= y) to templates. Templates return x; else return y; } Now we can write: cout right); cout value left) + countNodes(root->right); } Data Structures, Salah&Tamimi, 2022  More Examples of Binary Trees Count nodes: P We use recursion, remember the two questions about F S recursion! Trees B H R Y G T Z int countNodes(Node *root) { if (root == NULL) return 0; W else return 1 + countNodes(root->left) + countNodes(root->right); } Data Structures, Salah&Tamimi, 2022  More Examples of Binary Trees Depth of a binary tree: P We use recursion, remember the two questions about F S recursion! Trees B H R Y G T Z int depth(Node *root) { if (root == NULL) return -1; W else return 1 + max(depth(root->left), depth(root->right)); } Data Structures, Salah&Tamimi, 2022  More Examples of Binary Trees Depth = 4 Depth of a binary tree: P We use recursion, remember Depth = 2 Depth = 3 the two questions about F S recursion! Trees B H R Y G T Z int depth(Node *root) { if (root == NULL) return -1; W else return 1 + max(depth(root->left), depth(root->right)); } Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) BST: For any node, all value stored in the left subtree are less than or equal, and all value in the right subtree are greater than the value stored in the node 10 Trees 10 5 5 12 5 12 15 13 11 13 12 5 1 5 1 Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) BST: For any node, all value stored in the left subtree are less than or equal, and all value in the right subtree are greater than the value stored in the node X 10  Trees  5 5 10 12 5 12 15 13  5 11 13 X 12 1 5 1 Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) What is a BST good for? 15 Efficient to search for an element in the tree 14 18 Trees 10 17 5 12 1 11 13 Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) What is a BST good for? 15 Efficient to search for an element in the tree How to search for a value in a BST? 14 18 Trees If the tree is empty ➔ value can not be found 10 17 If the value is found in the root node ➔ done 5 12 If the value value) pos = root; else if (key value) 5 12 searchBST(root->left, key, pos); else searchBST(root->right, key, pos); 11 13 } Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) How to search for a value in a BST? 15 Non-recursive solution: NodePTR searchBST_NonRecursive(NodePTR root, int key) 14 18 { Trees NodePTR p = root; 10 17 while (p != NULL) { if (key == p->value) 5 12 return p; else if (key value) p = p->left; 11 13 else p = p->right; } return p; } Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) p Return a pointer to the node containing 15 the minimum value in a BST 14 18 Trees NodePTR minElementInBST(NodePTR root) { 17 10 NodePTR p = root; while (p->left != NULL) p = p->left; 5 12 return p; } 11 13 Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) Return a pointer to the node containing 15 the minimum value in a BST 14 18 Trees NodePTR minElementInBST(NodePTR root) { 17 10 NodePTR p = root; p while (p->left != NULL) p = p->left; 5 12 return p; } 11 13 Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) Return a pointer to the node containing 15 the minimum value in a BST 14 18 Trees NodePTR minElementInBST(NodePTR root) { 17 10 NodePTR p = root; p while (p->left != NULL) p = p->left; 5 12 return p; } 11 13 Problem? Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) Return a pointer to the node containing 15 the minimum value in a BST Better solution 14 18 Trees NodePTR minElementInBST(NodePTR root) { 17 10 if (root == NULL) return NULL; p NodePTR p = root; 5 12 while (p->left != NULL) p = p->left; 11 13 return p; } Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) Return a pointer to the node containing 15 the minimum value in a BST Better solution 14 18 Trees NodePTR minElementInBST(NodePTR root) { 17 10 if (root == NULL) return NULL; NodePTR p = root; 5 12 while (p->left != NULL) p = p->left; 11 13 return p; } Q: What about the maximum? Data Structures, Salah&Tamimi, 2022  Binary Search Tree (BST) Main program void main() { NodePTR tree1 = NULL; Trees createBST(tree1); traverseInOrder(tree1);... cout