C++: implement a non-recursive version or inorder traversal for binary tree. Ple

Question

C++:
implement a non-recursive version or inorder traversal for binary tree. Please implement the nonRecInorder() function as well as the levelOrder() function:
Important: -Use queue and stack STL of C++ not your own definition
-The algorithm of this non-recursive inorder traversal is listed as follows:
Create an TreeNode* stack while(true)
while(root is not nullptr){ push(root) root = root->left;
} if(stack is empty) break;
root = top(); pop();
print out the datum of root
root = root->right; }
-The algorithm of level order traversal is listed as follows.
Create a queue If(root is not nullptr) push root to the queue
While(queue is not empty){
temp = Dequeu()
Print out datum of temp
If left pointer of temp is not nullptr, push it to the queue
If right pointer of temp is not nullptr, push it to the queue }
#include <iostream> #include <stack> #include <queue>
using namespace std;
// Tree Node has data, left pointer, right pointer struct TreeNode { int datum; struct TreeNode* left; struct TreeNode* right; };
// create a new node with given value, left and right pointers are nullptr struct TreeNode* newTreeNode(int value) { struct TreeNode* node = new struct TreeNode; node->datum = value; node->left = nullptr; node->right = nullptr; return(node); }
// Non-recursive traverse a binary tree // print out the values by inorder // it uses stack to store the nodes void noRecInorder(TreeNode *root) {    }
// level order traversal // It uses queue to store the values of the next level void levelOrder(TreeNode *root){
}

// Driver program to test above functions int main() { /* Constructed binary tree is 100 / 9 10 / / 9 4 7 */ struct TreeNode *root = newTreeNode(100); root->left = newTreeNode(9); root->right = newTreeNode(10); root->left->left = newTreeNode(9); root->left->right = newTreeNode(4); root->right->left = newTreeNode(7);    cout << "Inorder traversal result:" << endl;; noRecInorder(root); cout << "Level traversal result:" << endl;    levelOrder(root);    return 0; } C++:
implement a non-recursive version or inorder traversal for binary tree. Please implement the nonRecInorder() function as well as the levelOrder() function:
Important: -Use queue and stack STL of C++ not your own definition
-The algorithm of this non-recursive inorder traversal is listed as follows:
Create an TreeNode* stack while(true)
while(root is not nullptr){ push(root) root = root->left;
} if(stack is empty) break;
root = top(); pop();
print out the datum of root
root = root->right; }
-The algorithm of level order traversal is listed as follows.
Create a queue If(root is not nullptr) push root to the queue
While(queue is not empty){
temp = Dequeu()
Print out datum of temp
If left pointer of temp is not nullptr, push it to the queue
If right pointer of temp is not nullptr, push it to the queue }
#include <iostream> #include <stack> #include <queue>
using namespace std;
// Tree Node has data, left pointer, right pointer struct TreeNode { int datum; struct TreeNode* left; struct TreeNode* right; };
// create a new node with given value, left and right pointers are nullptr struct TreeNode* newTreeNode(int value) { struct TreeNode* node = new struct TreeNode; node->datum = value; node->left = nullptr; node->right = nullptr; return(node); }
// Non-recursive traverse a binary tree // print out the values by inorder // it uses stack to store the nodes void noRecInorder(TreeNode *root) {    }
// level order traversal // It uses queue to store the values of the next level void levelOrder(TreeNode *root){
}

// Driver program to test above functions int main() { /* Constructed binary tree is 100 / 9 10 / / 9 4 7 */ struct TreeNode *root = newTreeNode(100); root->left = newTreeNode(9); root->right = newTreeNode(10); root->left->left = newTreeNode(9); root->left->right = newTreeNode(4); root->right->left = newTreeNode(7);    cout << "Inorder traversal result:" << endl;; noRecInorder(root); cout << "Level traversal result:" << endl;    levelOrder(root);    return 0; } C++:
implement a non-recursive version or inorder traversal for binary tree. Please implement the nonRecInorder() function as well as the levelOrder() function:
Important: -Use queue and stack STL of C++ not your own definition
-The algorithm of this non-recursive inorder traversal is listed as follows:
Create an TreeNode* stack while(true)
while(root is not nullptr){ push(root) root = root->left;
} if(stack is empty) break;
root = top(); pop();
print out the datum of root
root = root->right; }
-The algorithm of level order traversal is listed as follows.
Create a queue If(root is not nullptr) push root to the queue
While(queue is not empty){
temp = Dequeu()
Print out datum of temp
If left pointer of temp is not nullptr, push it to the queue
If right pointer of temp is not nullptr, push it to the queue }
#include <iostream> #include <stack> #include <queue>
using namespace std;
// Tree Node has data, left pointer, right pointer struct TreeNode { int datum; struct TreeNode* left; struct TreeNode* right; };
// create a new node with given value, left and right pointers are nullptr struct TreeNode* newTreeNode(int value) { struct TreeNode* node = new struct TreeNode; node->datum = value; node->left = nullptr; node->right = nullptr; return(node); }
// Non-recursive traverse a binary tree // print out the values by inorder // it uses stack to store the nodes void noRecInorder(TreeNode *root) {    }
// level order traversal // It uses queue to store the values of the next level void levelOrder(TreeNode *root){
}

// Driver program to test above functions int main() { /* Constructed binary tree is 100 / 9 10 / / 9 4 7 */ struct TreeNode *root = newTreeNode(100); root->left = newTreeNode(9); root->right = newTreeNode(10); root->left->left = newTreeNode(9); root->left->right = newTreeNode(4); root->right->left = newTreeNode(7);    cout << "Inorder traversal result:" << endl;; noRecInorder(root); cout << "Level traversal result:" << endl;    levelOrder(root);    return 0; }

Explanation / Answer

//============================================================================
// Name : tree2.cpp
// Author : pandurang
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <stack>

using namespace std;

struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* Node(int data)
{
struct node* node = new struct node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}

void Inorder(node *root)
{

if (root == NULL)
return;

// Create an empty stack and push root to it
stack<node *> Stacknode;
Stacknode.push(root);

/* Pop all items one by one. Do following for every popped item
a) push its left child
b) print data
c)push its right child*/

while (Stacknode.empty() == false)
{
// Pop the top item from stack and print it
struct node *node = Stacknode.top();

Stacknode.pop();

if (node->left)
Stacknode.push(node->left);

printf ("%d ", node->data);

if (node->right)
Stacknode.push(node->right);

}
}

int main()
{
/* Constructed binary tree is
100
/
9 10
/ /
9 4 7
*/
struct node *root = Node(100);
root->left = Node(9);
root->right = Node(10);
root->left->left = Node(9);
root->left->right = Node(4);
root->right->left = Node(7);
Inorder(root);
return 0;
}

**************************************************************************************************************

OutPut

9 9 4 100 7 10

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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