Learn C++ Programming Language
Binary Trees in C++ programming
Binary tree data structures
Binary trees differ from linked lists in that where a node in a linked list may have at most one successor, a node in a binary tree can have up to two successors.
A binary tree is a collection of nodes in which each node is associated with up to two successor nodes, respectively called the left and right child.
Not every node in the binary tree will have two children: one or both nodes may be omitted. A node in a binary tree that has no children is called a leaf node.
A node that has children is said to be the parent of its children. For a nonempty collection of nodes to qualify as a binary tree, every node must have at most one parent, and there must be exactly one node with no parent.
The one node that has no parent is called the root of the binary tree. An empty collection of nodes is regarded as constituting an empty binary tree.
Implementation of binary trees
Binary trees are used to store values in their nodes. A node in a binary tree will therefore be a structure or class object that contains a member for storing the value, as well as two members that point to nodes that are the left and right children of that node:
struct TreeNode
{
int value;
TreeNode *left;
TreeNode *right;
};
A binary tree is itself represented by a pointer to the node that is the root of the tree. An example binary tree, with the values stored in the nodes not shown, is illustrated in below.
The left or right pointer in a node is set to NULL if that node does not possess the corresponding child.
An example of binary tree
Binary search trees may be implemented as templates, but any data types used with them must support the <, >, and == operators.
The actual implementation of a binary tree template has been left as a examples to demonstrates for you. If you use the tree to store class objects, these operators must be overridden.
The following program uses a generalization of binary trees to build genealogy trees.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
enum Gender{male, female};
class Person {
string name;
Gender gender;
vector<Person *> parents;
vector<Person *> children;
void addParent(Person *p){ parents.push_back(p); }
public:
Person (string name, Gender g) {
this->name = name;
gender = g;
}
Person *addChild(string name, Gender g);
Person *addChild(Person *p);
friend ostream &operator << (ostream &out, Person p);
// Member functions for getting various Person info
string getName(){ return name; };
Gender getGender(){ return gender; };
int getNumChildren(){ return children.size(); }
int getNumParents(){ return parents.size(); }
Person *getChild(int k);
Person *getParent(int k);
};
Person *Person::addChild(string name, Gender g) {
Person *child = new Person(name, g);
child->addParent(this); // I am a parent of this child
children.push_back(child); // This is one of my children
return child;
}
Person *Person::addChild(Person* child){
child->addParent(this); // I am a parent of this child
children.push_back(child); // This is one of my children
return child;
}
Person *Person::getParent(int k){
if (k < 0 || k >= parents.size()) {
cout << "Error indexing parents vector." << endl;
exit(1);
} return parents[k];
}
Person *Person::getChild(int k) {
if (k < 0 || k >= children.size()) {
cout << "Error indexing children's vector." << endl;
exit(1);
} return children[k];
}
ostream & operator<<(ostream & out, Person p) {
out << "<person name = " << p.name << ">" << '\n';
if (p.parents.size() > 0)
out << " <parents>" << ' ';
for (int k = 0; k < p.parents.size(); k++) {
out << " " << p.parents[k]->name << ' ';
}
if (p.parents.size() > 0)
out << " </parents>" << "\n";
if (p.children.size() > 0)
out << " <children>" << ' ';
for (int k = 0; k < p.children.size(); k++) {
out << " " << p.children[k]->name << ' ';
}
if (p.children.size() > 0)
out << " </children>" << "\n";
out << "</person>" << "\n";
return out;
} int main(int argc, char** argv) {
// Here are the people
Person adam("Adam", male);
Person eve("Eve", female);
Person joan("Joan", female);
// Adam and Eve are parents of Abel
Person *pAbel = eve.addChild(new Person("Abel", male));
adam.addChild(pAbel);
// Abel and Joan are parents of Missy
Person *pMissy = joan.addChild("Missy", female);
pAbel->addChild(pMissy);
// Output all the people
cout << "Here are all the people:\n\n";
cout << adam << eve";
cout << *pAbel << joan;
cout << *pMissy << "\n";
// Print parents of Missy
cout << "Missy's parents are: " << endl;
for (unsigned int k = 0; k < pMissy->getNumParents(); k++) {
Person * p = pMissy->getParent(k);
switch(p->getGender()) {
case female : cout << "\tMother: "; break;
case male: cout << "\tFather: "; break;
}
cout << p->getName() << endl;
}
return 0;
}
Program Output :
Here are all the people:
<person name = Adam>
<children> Abel </children></person>
<person name = Eve>
<children> Abel </children></person>
<person name = Abel>
<parents> Eve Adam </parents>
<children> Missy </children></person>
<person name = Joan>
<children> Missy </children></person>
<person name = Missy>
<parents> Joan Abel </parents></person>
Missy's parents are:
Mother: Joan
Father: Abel
Ads Right