Using the binary_tree_node from textbook, write an iterative function (no recurs

Question

Using the binary_tree_node from textbook, write an iterative function (no recursion) to meet the following specification. You do not need to check the precondition. Make the function as efficient as possible (do not visit nodes unnecessarily):

template<class Item>

int max(binary_tree_node* root_ptr)

// Precondition: root_ptr is the root pointer of a nonempty binary SEARCH tree.

486 Chapter 10/ Trees With the binary tree node definition in hand, we can define a small collection of functions for creating and manipulating trees. Primarily, the functions are meant to help a programmer who is writing a class that uses a binary tree to store data. The functions are similar to the linked-list functions that we wrote in Chap- ter 5 and subsequently used in linked-list versions of the bag class, sequence class, stack class, and queue class. We will start with only two functions, but we'l add more later FIGURE 10.6 The Binary Tree Node Definition A Class Definition template class binary tree_node public: // TYPEDEF typedef Item value_type /I CONSTRUCTOR binarytree node( const Item& init dataItem(, binary tree_node init.left NULL binary tree_node init rightNULL data fieldinit data; left-field = i ni t-left ; right field init right; /I MODIFICATION MEMBER FUNCTIONS Item& data() return data_field; binary tree_node & left return left field; 1 binary tree_node*& right() return right field; 1 void set_data(const Item& new_data) data field new_data; void set left (binary tree_node new left) left field- new left; void set right(binary_tree_node new right) right field new right; // CONSTANT MEMBER FUNCTIONS const Item& data const return data field; ) const binary_tree node* left() const return left field; const binary_tree_node* right) const return right field; h bool is leaf const return (left field NULL)&& (right field NULL); private: Item data field; binary tree_node 1eft field; binary tree_node *right field; www.cs.colorado.eduf-main/chapter10/bintree.h www

Explanation / Answer

// Precondition: root_ptr is the root pointer of a nonempty binary SEARCH tree. // Postcondition: The return value is the largest value in the tree. template int max(binary_tree_node* root_ptr) { while(root_ptr->right() != NULL) { root_ptr = root_ptr->right(); } return root_ptr->data(); }

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.