[JAVA] 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

Recommended Posts

Binary tree memorandum for beginners (Part 3 Realization using class)
Binary Tree Memorandum for Beginners (Part 1)
Binary tree memorandum for beginners (Part 4 Binary heap)
Binary tree memorandum for beginners (Part 5 Binary search tree)
Binary tree memorandum for beginners (Part 2 Search for binary trees)
CI / CD practice for beginners --Part1 --Environment construction
CI / CD practice for beginners --Part3 --Preparation for development project
Experience CI / CD with katacoda (for beginners) --Part10 (Building Docker Images using Jenkins)
Binary Tree Memorandum for Beginners (Part 1)
Environment construction with Docker for beginners
Binary tree memorandum for beginners (Part 4 Binary heap)
Binary tree memorandum for beginners (Part 5 Binary search tree)
Binary tree memorandum for beginners (Part 2 Search for binary trees)
java practice part 1
Binary tree memorandum for beginners (Part 3 Realization using class)
A memorandum for android application development beginners
Experience CI / CD with katacoda (for beginners) --Part10 (Building Docker Images using Jenkins)
[For beginners] I tried using DBUnit in Eclipse
[For beginners] I tried using JUnit 5 in Eclipse
CI / CD practice for beginners --Part1 --Environment construction
Beginners try using android studio Part 2 (event processing)
Beginners try using android studio Part 1 (Hello World)
[For beginners] Procedure for creating a controller using rails