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