Skip to content

Instantly share code, notes, and snippets.

@ygabo
Created June 14, 2013 11:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ygabo/5781211 to your computer and use it in GitHub Desktop.
Save ygabo/5781211 to your computer and use it in GitHub Desktop.
Binary Tree inserting, print in-order, print by level, find next node in-order.
#include <vector>
#include <iostream>
#include <random>
#include <time.h>
#include <queue>
using namespace std;
class Node{
public:
Node():data(0),left(nullptr),right(nullptr),parent(nullptr) {}
Node(int x):data(x),left(nullptr),right(nullptr),parent(nullptr) {}
Node * left;
Node * right;
Node * parent;
int data;
};
class Tree{
public:
Tree():head(nullptr){}
Tree(Node * n):head(n){}
Node * insert(int x){
if(!head){
head = new Node(x);
return head;
}
insert(head, nullptr, x);
}
void print(){
print(head);
cout<<endl;
}
void print_level(){
d.push_back( new queue<Node*>);
d.push_back( new queue<Node*>);
print_by_level(head, 0);
cout << endl;
}
Node * find( int x ){
return find_recurse(head, x);
}
Node * next_node_in_order( Node * n ){
Node *temp, *rent;
temp = n->right;
if( temp ){
while( temp->left )
temp = temp->left;
return temp;
}
else{
temp = n;
rent = n->parent;
while( rent && (rent->right == n ) ){
n = rent;
rent = n->parent;
}
return rent;
}
}
private:
Node * head;
vector<queue<Node *>*> d;
Node * find_recurse( Node * n, int x ){
if( !n )
return nullptr;
if( n->data == x )
return n;
else if( x < n->data )
return find_recurse( n->left, x);
else
return find_recurse( n->right, x);
}
void print_by_level(Node * n, int level){
if( !n ) return;
if( n->left) d[(level+1)%2]->push(n->left);
if( n->right) d[(level+1)%2]->push(n->right);
cout << n->data << "(" << level << ")";
if( !d[level%2]->empty() ){
n = d[level%2]->front();
d[level%2]->pop();
}
else if( !d[(level+1)%2]->empty() ){
n = d[(level+1)%2]->front();
d[(level+1)%2]->pop();
level++;
cout << endl;
}
else
return;
print_by_level(n, level);
}
void insert(Node* &n, Node* parent, int x){
if(!n){
n = new Node(x);
n->parent = parent;
return;
}
if( x < n->data )
insert( n->left,n, x);
else if( x > n->data)
insert(n->right,n, x);
else
return;
}
void print( Node * head){
if( !head ) return;
print( head->left);
cout << head->data << " ";
print( head->right);
}
};
void main(){
srand(time(0));
Tree tree;
int x[] = { 10, 4, 3, 9, 3, 12, 11, 14, 16 };
for( int i = 0; i < (sizeof(x)/sizeof(x[0])); ++i){
tree.insert(x[i]);
}cout <<endl;
tree.print();
cout<<endl;
tree.print_level();
Node *n = tree.find(14);
cout << n->data << endl;
n = tree.next_node_in_order(n);
cout << n->data << endl;
cin.get();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment