Basic Binary Tree data Structure.

[avansc]

here is a C++ implementation of a binary tree. binary trees are very powerful tools.

Code: Select all

#include <iostream>

using namespace  std;

typedef struct node
{
	int val;
	node *rNode;
	node *lNode;
} node;

class bTree
{
public:
	bTree();
	node *add_Node(node *tRoot, int data);
	void print_Tree(node *tree);

	node *root;
};

bTree::bTree()
{
	this->root = new node;
	this->root = NULL;
	cout << "Tree Created." << endl;
}

node *bTree::add_Node(node *tRoot, int data)
{
	if(tRoot == NULL)
	{
		tRoot=new node;
		tRoot->lNode = NULL;
		tRoot->rNode = NULL;
		tRoot->val = data;
	}else
	if(data < tRoot->val)
		tRoot->lNode = this->add_Node(tRoot->lNode, data);
	else
		tRoot->rNode = this->add_Node(tRoot->rNode, data);
	return tRoot;
}

void bTree::print_Tree(node* tree)
{
	if(tree != NULL)
	{
		this->print_Tree(tree->lNode);
		cout<< tree->val << endl;
		this->print_Tree(tree->rNode);
	}
}

int main(void)
{
	cout << "Start of program" << endl;
	bTree* tree = new bTree();
	tree->root = tree->add_Node(tree->root, 100);
	tree->root = tree->add_Node(tree->root, 12);
	tree->root = tree->add_Node(tree->root, 1040);
	tree->root = tree->add_Node(tree->root, 1023);
	tree->root = tree->add_Node(tree->root, 1450);
	tree->root = tree->add_Node(tree->root, 1);
	tree->root = tree->add_Node(tree->root, 156);
	tree->root = tree->add_Node(tree->root, 10222);
	tree->root = tree->add_Node(tree->root, 130);
	tree->root = tree->add_Node(tree->root, 156);
	tree->root = tree->add_Node(tree->root, 2);
	tree->root = tree->add_Node(tree->root, 101);
	tree->print_Tree(tree->root);
	cin.get();
}

i didn't comment anything, sorry. if you have any questions please feel free to ask. the recursive function might be hard to understand at first.
it traverses the tree in "inorder" other options are pre, and postorder, but will not yeild the correct output. but is still interesting to look at.

[Arce]

Now make it completely self-sorting and sufficient using smart-pointers and templates--naw, heckling ya. ;P

I'll take a look at it when I've got more time. I've never seen the 'formal way' (if one exists) to implement one. I've read up on the theory, and everyone I've used I created my own algorithm (also involving recursion) for.

[avansc]

Now make it completely self-sorting and sufficient using smart-pointers and templates--naw, heckling ya. ;P

I'll take a look at it when I've got more time. I've never seen the 'formal way' (if one exists) to implement one. I've read up on the theory, and everyone I've used I created my own algorithm (also involving recursion) for.

"self sorting" thats a property of a binary tree. it sorts as you add nodes.

and im not sure why you said "smart pointers"

this is what smart pointers are.

Smart pointers are objects which store pointers to dynamically allocated (heap) objects. They behave much like built-in C++ pointers except that they automatically delete the object pointed to at the appropriate time. Smart pointers are particularly useful in the face of exceptions as they ensure proper destruction of dynamically allocated objects. They can also be used to keep track of dynamically allocated objects shared by multiple owners.

[Arce]

"self sorting" thats a property of a binary tree. it sorts as you add nodes.

Ha, true.

and im not sure why you said "smart pointers"

this is what smart pointers are.

You're obviously not storing 'data' as I envisioned you would be. With the given code, how would you implement this into a practical application? Atm, data is an int; I was picturing 'data' being a pointer to some other object and the comparison being overloaded. Is the intent of this to have a class inherit a node or tree? Or are you supposed to add additional data as members of a node?

Also, is there any particular reason this is done in C++ with C? Why is node a C style struct?

Also, nice job with the tutorials! You're whipping those things out like crazy. ;p

[sparda]

Yeah, binary trees are awesome! Contrariwise, I've been working with heaps in another compression program I'm writing. Heaps are more cumbersome to traverse because of their partial ordering. I know std::priority_queue uses heaps extensively, although they are really just generalized binary trees. Arce, smart pointers would be kinda overkill for simple data structures like this, no? Adding reference counts, releasing them, uh... kinda reminds me of Microsoft's component object model, which sucks the biggest balls ever. Although you could probably wrap a smart pointer functionality to this binary tree structure in no time.

[avansc]

"self sorting" thats a property of a binary tree. it sorts as you add nodes.

Ha, true.

and im not sure why you said "smart pointers"

this is what smart pointers are.

You're obviously not storing 'data' as I envisioned you would be. With the given code, how would you implement this into a practical application? Atm, data is an int; I was picturing 'data' being a pointer to some other object and the comparison being overloaded. Is the intent of this to have a class inherit a node or tree? Or are you supposed to add additional data as members of a node?

Also, is there any particular reason this is done in C++ with C? Why is node a C style struct?

Also, nice job with the tutorials! You're whipping those things out like crazy. ;p

all that that program does it it takes numbers in any order and dynamically sorts them in a tree. the data in the tree is just the int.
meh, i dont know, i like using C in C++. i can do it in straigt C or just C++. but i like mixing it up. its probably not good.

but using structure in C++ does not really mean you are reverting back to C. everything of C is a subset of C++.

[Arce]

Of course they would be. ;P

Hence,

Now make it completely self-sorting and sufficient using smart-pointers and templates--naw, heckling ya. ;P

I was just saying that I'm not completely stupid--I hadn't skimmed at hit code and assumed for some reason that the data was pointers vs ints. ;P

And yes, I've run into a few times where binary trees are actually practical (other than for solving advanced comp sci questions. ;P)

all that that program does it it takes numbers in any order and dynamically sorts them in a tree. the data in the tree is just the int.
meh, i dont know, i like using C in C++. i can do it in straigt C or just C++. but i like mixing it up. its probably not good.

but using structure in C++ does not really mean you are reverting back to C. everything of C is a subset of C++.

Just curious--an interesting habit. ;P