Part 3 is here
So far, I have explained the outline of the binary tree. From this time, I will explain a concrete example of a binary tree. The first example is a binary tree called a binary heap. The structure is simple, it's just a complete binary tree whose parent data is always smaller than the child data. A complete binary tree was a binary tree with no vacancy at the nodes that were not leaves, and all the leaves were left-justified. Since the binary heap is a kind of complete binary tree, it can be realized by using an array.
C++
BinaryHeap.cpp
#include <iostream>
using namespace std;
void breadthFirstSearch(int binaryTree[], int nodeNum);
int insertNode(int binaryHeap[], int value, int nodeNum);
int deleteNode(int binaryHeap[], int value, int nodeNum);
int searchNode(int binaryHeap[], int value, int nodeNum, int index);
//Function to display in the order of breadth-first search
void breadthFirstSearch(int binaryTree[], int nodeNum)
{
for (int i = 0; i < nodeNum; i++) {
cout << binaryTree[i] << " ";
}
cout << endl;
}
//A function that inserts a new node into the binary heap
//Returns 1 on success, 0 on failure
int insertNode(int binaryHeap[], int value, int nodeNum)
{
//Do nothing if there is already value
if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
return 0;
}
//Temporarily inserted at the end
binaryHeap[nodeNum] = value;
int i = nodeNum;
//Follow from the tail to the root
while (i > 0) {
//If the parent is bigger
if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
//Exchange parents and children
binaryHeap[i] = binaryHeap[(i - 1) / 2];
binaryHeap[(i - 1) / 2] = value;
i = (i - 1) / 2;
}
//If the parent is smaller
else {
return 1;
}
}
return 1;
}
//A function that removes nodes with value in the data from the binary heap
//Returns 1 on success, 0 on failure
int deleteNode(int binaryHeap[], int value, int nodeNum)
{
int index = searchNode(binaryHeap, value, nodeNum, 0);
//Do nothing if there is no value in the binaryHeap
if (index == -1) {
return 0;
}
//Temporarily move the last data
binaryHeap[index] = binaryHeap[nodeNum - 1];
// binaryHeap[index]Loop as long as there are children
//Note that the total number of nodes has been reduced by one.
while (2 * index + 1 < nodeNum - 1) {
int childIndex, childValue;
//If there is only the left child
if (2 * index + 1 == nodeNum - 2) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//If you have left and right children
else {
//If the child on the left is smaller
if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//If the right child is smaller
else {
childIndex = 2 * index + 2;
childValue = binaryHeap[2 * index + 2];
}
}
//Compare your current position with the smaller child
//If the current position is larger
if (binaryHeap[index] > childValue) {
//Swap the current position and child
binaryHeap[childIndex] = binaryHeap[index];
binaryHeap[index] = childValue;
index = childIndex;
}
//If the child is larger
else {
return 1;
}
}
return 1;
}
//A function that searches the binary heap for nodes that have value in the data
//Index of the node if successful, if unsuccessful-Returns 1
int searchNode(int binaryHeap[], int value, int nodeNum, int index)
{
//Do nothing if the number of nodes is 0
if (nodeNum == 0) {
return -1;
}
//Scan in the order of destination
//Successful search
if (binaryHeap[index] == value) {
return index;
}
//Search failure
else if (binaryHeap[index] > value) {
return -1;
}
//Still continue
else {
int leftResult = -1, rightResult = -1;
if (2 * index + 1 < nodeNum) {
leftResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 1);
}
if (2 * index + 2 < nodeNum) {
rightResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 2);
}
if (leftResult == -1 && rightResult == -1) {
return -1;
}
else if (leftResult != -1) {
return leftResult;
}
else {
return rightResult;
}
}
}
int main()
{
int binaryHeap[100];
int nodeNum = 0;
nodeNum += insertNode(binaryHeap, 8, nodeNum);
nodeNum += insertNode(binaryHeap, 12, nodeNum);
nodeNum += insertNode(binaryHeap, 19, nodeNum);
nodeNum += insertNode(binaryHeap, 9, nodeNum);
nodeNum += insertNode(binaryHeap, 4, nodeNum);
nodeNum += insertNode(binaryHeap, 21, nodeNum);
nodeNum += insertNode(binaryHeap, 2, nodeNum);
nodeNum += insertNode(binaryHeap, 14, nodeNum);
//Do not allow duplicate insertion
nodeNum += insertNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
cout << "nodeNum: " << nodeNum << endl;
int index = searchNode(binaryHeap, 14, nodeNum, 0);
cout << "index: " << index << ", value: " << binaryHeap[14] << endl;
//If you look for a node that does not exist-1 is back
index = searchNode(binaryHeap, 1, nodeNum, 0);
cout << "index: " << index << endl;
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
nodeNum -= deleteNode(binaryHeap, 2, nodeNum);
nodeNum -= deleteNode(binaryHeap, 21, nodeNum);
//You can't delete what you don't have
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
cout << "nodeNum: " << nodeNum << endl;
}
Java
BinaryHeap.java
public class BinaryHeapAnswer {
//Function to display in the order of breadth-first search
public static void breadthFirstSearch(int[] binaryTree, int nodeNum) {
for (int i = 0; i < nodeNum; i++) {
System.out.print(binaryTree[i] + " ");
}
System.out.println("");
}
//A function that inserts a new node into the binary heap
//Returns 1 on success, 0 on failure
public static int insertNode(int[] binaryHeap, int value, int nodeNum) {
//Do nothing if there is already value
if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
return 0;
}
//Temporarily inserted at the end
binaryHeap[nodeNum] = value;
int i = nodeNum;
//Follow from the tail to the root
while (i > 0) {
//If the parent is bigger
if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
//Exchange parents and children
binaryHeap[i] = binaryHeap[(i - 1) / 2];
binaryHeap[(i - 1) / 2] = value;
i = (i - 1) / 2;
}
//If the parent is smaller
else {
return 1;
}
}
return 1;
}
//A function that removes nodes with value in the data from the binary heap
//Returns 1 on success, 0 on failure
public static int deleteNode(int[] binaryHeap, int value, int nodeNum) {
int index = searchNode(binaryHeap, value, nodeNum, 0);
//Do nothing if there is no value in the binaryHeap
if (index == -1) {
return 0;
}
//Temporarily move the last data
binaryHeap[index] = binaryHeap[nodeNum - 1];
// binaryHeap[index]Loop as long as there are children
//Note that the total number of nodes has been reduced by one.
while (2 * index + 1 < nodeNum - 1) {
int childIndex, childValue;
//If there is only the left child
if (2 * index + 1 == nodeNum - 2) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//If you have left and right children
else {
//If the child on the left is smaller
if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//If the right child is smaller
else {
childIndex = 2 * index + 2;
childValue = binaryHeap[2 * index + 2];
}
}
//Compare your current position with the smaller child
//If the current position is larger
if (binaryHeap[index] > childValue) {
//Swap the current position and child
binaryHeap[childIndex] = binaryHeap[index];
binaryHeap[index] = childValue;
index = childIndex;
}
//If the child is larger
else {
return 1;
}
}
return 1;
}
//A function that searches the binary heap for nodes that have value in the data
//Index of the node if successful, if unsuccessful-Returns 1
public static int searchNode(int[] binaryHeap, int value, int nodeNum, int index) {
//Do nothing if the number of nodes is 0
if (nodeNum == 0) {
return -1;
}
//Scan in the order of destination
//Successful search
if (binaryHeap[index] == value) {
return index;
}
//Search failure
else if (binaryHeap[index] > value) {
return -1;
}
//Still continue
else {
int leftResult = -1, rightResult = -1;
if (2 * index + 1 < nodeNum) {
leftResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 1);
}
if (2 * index + 2 < nodeNum) {
rightResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 2);
}
if (leftResult == -1 && rightResult == -1) {
return -1;
}
else if (leftResult != -1) {
return leftResult;
}
else {
return rightResult;
}
}
}
public static void main(String[] args) {
int[] binaryHeap = new int[100];
int nodeNum = 0;
nodeNum += insertNode(binaryHeap, 8, nodeNum);
nodeNum += insertNode(binaryHeap, 12, nodeNum);
nodeNum += insertNode(binaryHeap, 19, nodeNum);
nodeNum += insertNode(binaryHeap, 9, nodeNum);
nodeNum += insertNode(binaryHeap, 4, nodeNum);
nodeNum += insertNode(binaryHeap, 21, nodeNum);
nodeNum += insertNode(binaryHeap, 2, nodeNum);
nodeNum += insertNode(binaryHeap, 14, nodeNum);
//Do not allow duplicate insertion
nodeNum += insertNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
System.out.println("nodeNum: " + nodeNum);
int index = searchNode(binaryHeap, 14, nodeNum, 0);
System.out.println("index: " + index + ", value: " + binaryHeap[14]);
//If you look for a node that does not exist-1 is back
index = searchNode(binaryHeap, 1, nodeNum, 0);
System.out.println("index: " + index);
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
nodeNum -= deleteNode(binaryHeap, 2, nodeNum);
nodeNum -= deleteNode(binaryHeap, 21, nodeNum);
//You can't delete what you don't have
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
System.out.println("nodeNum: " + nodeNum);
}
}
The execution result is as follows.
2 8 4 12 9 21 19 14
nodeNum: 8
index: 7, value: 0
index: -1
4 8 19 12 9
nodeNum: 5
The following functions are implemented in the above program.
--void breadthFirstSearch (int [] binaryTree, int nodeNum): A function that displays a binary tree in the order of breadth-first search. --int insertNode (int [] binaryHeap, int value, int nodeNum): A function that inserts a new node with value as data into the binary heap. --int searchNode (int [] binaryHeap, int value, int nodeNum): A function that searches the binary heap for nodes that have value as data. --int deleteNode (int [] binaryHeap, int value, int nodeNum): A function that deletes a node having value as data from the binary heap.
The searchNode function scans in the order of destination. In the binary heap, the child data is always larger than the parent data, so I try to return when the current node data is larger than the value.
In the insertNode function, first, the searchNode function is used to check whether there is a node in the binary heap that has value as data. If it already exists, it will return without creating a new node. If not, first add a node at the end of the array. Then compare the size with the parent for that position and, if the parent is larger, exchange itself with the parent. Repeat the previous operation until the current position becomes the root or the parent becomes smaller, and the insertion is completed.
Lastly, regarding the deleteNode function, I will explain the procedure for comparing nodes, which is a bottleneck when considering the operation of this function. First, compare which of the left and right children is smaller and remember the smaller one. If there is only the left child, remember the left child. By the way, since the binary heap is a complete binary tree, it is impossible to have only the right child. Next, compare which of the memorized child and the node at the current position is smaller. If the child is larger, it cannot move any further and will end the comparison. If the current position is larger, it will be replaced with the child, and that will be used as the current position to compare with the child again. Repeat this comparison, and if the current position is a leaf, end there.
Now, regarding the operation of the deleteNode function, first, use the searchNode function to get the index of the target node. Then move the last node to that position. All you have to do now is compare the node with the child and move it until it fits in the proper position.
It may have been a little difficult, but I hope you can understand the binary heap somehow. Next time, I will explain about binary search trees.
Part 5 is here
Recommended Posts