Untitled
unknown
c_cpp
7 months ago
2.9 kB
2
Indexable
Never
#include<iostream> #include <stack> //#include<bits/stdc++.h> using namespace std; class Node { public: int value; Node* left; Node* right; Node(int value) { this->value=value; this->left=left; this->right=right; } }; void insert(Node*& root, int a) { Node* node=new Node(a); if(!root) { root=node; return; } Node* prev=NULL; Node* temp=root; while(temp) { if(temp->value>a) { prev=temp; temp=temp->left; } else if(temp->value<a) { prev=temp; temp=temp->right; } } if(prev->value>a) { prev->left=node; } else { prev->right=node; } } void inorder(Node* root) { if (!root) { return; } inorder(root->left); cout<<root->value<<" "; inorder(root->right); } void inorder_iteratively(Node * root) { stack<Node *> st; Node * at = root; while(at or !st.empty()) { while(at) { st.push(at); at = at->left; } at = st.top(); st.pop(); cout << at->value << " " ; at=at->right; } } void preorder(Node* root) { if (!root) { return; } cout<<root->value<<" "; preorder(root->left); preorder(root->right); } void preorder_iteratively(Node * root) { if(!root) { return; } stack<Node *> st; st.push(root); while(!st.empty()) { Node * c = st.top(); st.pop(); cout << c->value << " "; if(c->right) { st.push(c->right); } if(c->left) { st.push(c->left); } } } void postorder(Node* root) { if (!root) { return; } postorder(root->left); postorder(root->right); cout<<root->value<<" "; } void postorder_iteratively(Node * root) { if(!root) { return; } stack<Node * > st; Node * at = root; Node * visited = NULL; while(at or !st.empty()) { while(at) { st.push(at); at = at->left; } Node * c = st.top(); if(c->right and c->right != visited) { at = c->right; } else { cout << c->value << " "; st.pop(); visited = c; } } } int main() { Node* root = new Node(6); insert(root, 8); insert(root, 2); insert(root, 1); insert(root, 4); insert(root, 3); insert(root, 7); cout<<"Inorder:"; inorder(root); cout<<endl; inorder_iteratively(root); cout<<"Preorder:"; preorder(root); cout<<endl; preorder_iteratively(root); cout<<"Postorder:"; postorder(root); cout << endl; postorder_iteratively(root); return 0; }
Leave a Comment