Skip to content

Instantly share code, notes, and snippets.

@toboqus
Created November 3, 2015 08:53
Show Gist options
  • Save toboqus/def6a6915e4abd66e922 to your computer and use it in GitHub Desktop.
Save toboqus/def6a6915e4abd66e922 to your computer and use it in GitHub Desktop.
Binary tree implementation in c++
#include <iostream>
using namespace std;
struct node{
int value;
node *left;
node *right;
};
class btree{
public:
btree();
~btree();
void insert(int key);
node *search(int key);
void destroy_tree();
void inorder_print();
void postorder_print();
void preorder_print();
private:
void destroy_tree(node *leaf);
void insert(int key, node *leaf);
node *search(int key, node *leaf);
void inorder_print(node *leaf);
void postorder_print(node *leaf);
void preorder_print(node *leaf);
node *root;
};
btree::btree(){
root = NULL;
}
btree::~btree(){
destroy_tree();
}
void btree::destroy_tree(node *leaf){
if(leaf != NULL){
destroy_tree(leaf->left);
destroy_tree(leaf->right);
delete leaf;
}
}
void btree::insert(int key, node *leaf){
if(key < leaf->value){
if(leaf->left != NULL){
insert(key, leaf->left);
}else{
leaf->left = new node;
leaf->left->value = key;
leaf->left->left = NULL;
leaf->left->right = NULL;
}
}else if(key >= leaf->value){
if(leaf->right != NULL){
insert(key, leaf->right);
}else{
leaf->right = new node;
leaf->right->value = key;
leaf->right->right = NULL;
leaf->right->left = NULL;
}
}
}
void btree::insert(int key){
if(root != NULL){
insert(key, root);
}else{
root = new node;
root->value = key;
root->left = NULL;
root->right = NULL;
}
}
node *btree::search(int key, node *leaf){
if(leaf != NULL){
if(key == leaf->value){
return leaf;
}
if(key < leaf->value){
return search(key, leaf->left);
}else{
return search(key, leaf->right);
}
}else{
return NULL;
}
}
node *btree::search(int key){
return search(key, root);
}
void btree::destroy_tree(){
destroy_tree(root);
}
void btree::inorder_print(){
inorder_print(root);
cout << "\n";
}
void btree::inorder_print(node *leaf){
if(leaf != NULL){
inorder_print(leaf->left);
cout << leaf->value << ",";
inorder_print(leaf->right);
}
}
void btree::postorder_print(){
postorder_print(root);
cout << "\n";
}
void btree::postorder_print(node *leaf){
if(leaf != NULL){
inorder_print(leaf->left);
inorder_print(leaf->right);
cout << leaf->value << ",";
}
}
void btree::preorder_print(){
preorder_print(root);
cout << "\n";
}
void btree::preorder_print(node *leaf){
if(leaf != NULL){
cout << leaf->value << ",";
inorder_print(leaf->left);
inorder_print(leaf->right);
}
}
int main(){
//btree tree;
btree *tree = new btree();
tree->insert(10);
tree->insert(6);
tree->insert(14);
tree->insert(5);
tree->insert(8);
tree->insert(11);
tree->insert(18);
tree->preorder_print();
tree->inorder_print();
tree->postorder_print();
delete tree;
}
@He1ler
Copy link

He1ler commented Nov 6, 2020

you have mistakes in "print" functions, you use always inorder traversal, but you have to use recursion in that function.

@Nabeel-Malkani
Copy link

Nabeel-Malkani commented Nov 6, 2020 via email

@He1ler
Copy link

He1ler commented Nov 11, 2020

In this function:
void btree::inorder_print(node leaf){
if(leaf != NULL){
inorder_print(leaf->left);
cout << leaf->value << ",";
inorder_print(leaf->right);
}
}
void btree::postorder_print(node leaf){
if(leaf != NULL){
inorder_print(leaf->left);
inorder_print(leaf->right);
cout << leaf->value << ",";
}
}
void btree::preorder_print(node leaf){
if(leaf != NULL){
cout << leaf->value << ",";
inorder_print(leaf->left);
inorder_print(leaf->right);
}
} You use always inorder_print, but you should use themselfs, like this :
void inorder_print(Node
leaf)
{
if (leaf != NULL)
{
inorder_print(leaf->left);
cout << leaf->data << ", ";
inorder_print(leaf->right);
}
}
void postorder_print(Node
leaf)
{
if (leaf != NULL)
{
postorder_print(leaf->left);
postorder_print(leaf->right);
cout << leaf->data << ", ";
}
}
void preorder_print(Node
leaf)
{
if (leaf != NULL)
{
cout << leaf->data << ", ";
preorder_print(leaf->left);
preorder_print(leaf->right);
}
}
This function will order rules of tree traversals. Am I right?

@akshadagrawal
Copy link

why you didn't used search function??
Why did u even made them if u didn't wanted to use it??

Aise hi sexy lag raha tha!!!

@Ivanskl
Copy link

Ivanskl commented Jun 30, 2021

Man there is a big mistake in your code. Here:
void btree::preorder_print(node *leaf){
if(leaf != NULL){
cout << leaf->value << ",";
inorder_print(leaf->left);
inorder_print(leaf->right);
}
}

You use "inorder_print" inside "preorder_print". Rightly:
void btree::preorder_print(node *leaf){
if(leaf != NULL){
cout << leaf->value << ",";
preorder_print(leaf->left);
preorder_print(leaf->right);
}
}

The same within "postorder_print". Correct please.

@seaque
Copy link

seaque commented Apr 8, 2022

Man there is a big mistake in your code. Here: void btree::preorder_print(node *leaf){ if(leaf != NULL){ cout << leaf->value << ","; inorder_print(leaf->left); inorder_print(leaf->right); } }

You use "inorder_print" inside "preorder_print". Rightly: void btree::preorder_print(node *leaf){ if(leaf != NULL){ cout << leaf->value << ","; preorder_print(leaf->left); preorder_print(leaf->right); } }

The same within "postorder_print". Correct please.

Please use markdown, especially for code blocks. Makes it easier to read.

Github basic writing and formatting

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment