Binary tree memorandum for beginners (Part 3 Realization using class)

Part 2 is here

Realization of a binary tree using a class

This time, let's realize a binary tree in a different way than before. A binary tree is a collection of nodes and edges. In other words, if you can create an object that represents a node and an edge, you can realize a binary tree by connecting them. In other words, all you have to do is create a class with node data and left and right children in the fields.

Implementation example

C++

BinaryTree.cpp

#include <iostream>
using namespace std;

class BinaryTree
{
	int value;
	BinaryTree *left;
	BinaryTree *right;

public:
 	BinaryTree(int);
	~BinaryTree();
	void insertNode(int);
	void inorder() const;
};

BinaryTree::BinaryTree(int value):value(value), left(0), right(0){}

BinaryTree::~BinaryTree()
{
	delete left;
	delete right;
}

void BinaryTree::insertNode(int value)
{
	if (this->value == value) {
		return;
	}

	else if (this->value > value) {
		if (this->left == 0) {
			this->left = new BinaryTree(value);
			return;
		}
		else {
			this->left->insertNode(value);
		}
	}

	else {
		if (this->right == 0) {
			this->right = new BinaryTree(value);
			return;
		}
		else {
			this->right->insertNode(value);
		}
	}
}

void BinaryTree::inorder() const
{
	if (this->left != 0) {
		this->left->inorder();
	}
	cout << this->value << " ";
	if (this->right != 0) {
		this->right->inorder();
	}

	return;
}

int main()
{
	BinaryTree root(20);
	root.insertNode(10);
	root.insertNode(26);
	root.insertNode(5);
	root.insertNode(14);
	root.insertNode(23);
	root.insertNode(25);

	root.inorder();
	cout << endl;
}

Java

BinaryTree.java

public class BinaryTree {
	int value;
	BinaryTree left;
	BinaryTree right;

	BinaryTree(int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}

	void insertNode(int value) {
		if (this.value == value) {
			return;
		}

		else if (this.value > value) {
			if (this.left == null) {
				this.left = new BinaryTree(value);
				return;
			}
			else {
				this.left.insertNode(value);
			}
		}

		else {
			if (this.right == null) {
				this.right = new BinaryTree(value);
				return;
			}
			else {
				this.right.insertNode(value);
			}
		}
	}

	void inorder() {
		if (this.left != null) {
			this.left.inorder();
		}
		System.out.print(this.value + " ");
		if (this.right != null) {
			this.right.inorder();
		}

		return;
	}

	public static void main(String[] args) {
		BinaryTree root = new BinaryTree(20);
		root.insertNode(10);
		root.insertNode(26);
		root.insertNode(5);
		root.insertNode(14);
		root.insertNode(23);
		root.insertNode(25);

		root.inorder();
		System.out.println();
	}
}

Explanation about implementation

The binary tree formed by the insertNode function in this program is especially called a binary search tree (don't ponder the insertNode function as it is not important this time). A binary search tree is a special binary tree in which the data of the left child is always smaller than the data of the parent and the data of the child on the right is always larger than the data of the parent (a detailed explanation of the binary search tree is Part 5. The results of searching the created binary tree in the order of passing are as follows.

5 10 14 20 23 25 26

Did you understand how to implement using classes?

Part 4 is here