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;
}
@infyProductions
Copy link

could someone explain how this works because it is understandable but having some comments makes everyone can understand how this code works

@SebastianWilke
Copy link

could someone explain how this works because it is understandable but having some comments makes everyone can understand how this code works

What exactly is it that you don't understand?

@infyProductions
Copy link

infyProductions commented Oct 1, 2019 via email

@lokfried
Copy link

lokfried commented Oct 6, 2019

Thank you very much. It is easy to understand.

@shabbarfatima
Copy link

good work .its really helpful.

@Nabeel-Malkani
Copy link

Why every function is defined twice. I didn't understand

@Nabeel-Malkani
Copy link

Like this

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 << ",";
}
}

every function is defined twicw. Any specific reason????????????

@SebastianWilke
Copy link

Like this

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 << ",";
}
}

every function is defined twicw. Any specific reason????????????

As you can see the first one is a public function, the second one is a private function. Usually you let users call the public functions which in turn call private functions that have access to private members and data. You can think of the public functions as an interface. For 'private' use this isn't necessary.
See Encapsulation (computer programming)

@SaifiLala
Copy link

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

@ravi8190
Copy link

how to do this for while taking user inputs?

@mudasirhw
Copy link

good work .its really helpful.

it is a binary search tree actually,, not binary tree. becoz in a binary tree there is n need to comapre a key while insertion.

@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