Binary tree memorandum for beginners (Part 2 Search for binary trees)

Part 1 is here

Binary tree search

When using data structures, you need to be able to search for data. In Binary Tree, there are two main search policies. Breadth-first search and depth-first search.

Breadth-first search

Breadth-first search refers to a search that looks in order from the one closest to the root.

Depth-first search

Depth-first search refers to a search that traces a tree along a side. There are three types of depth-first search: preorder, inorder, and postorder. In the order of arrival, first look at the parent, then the left child, and finally the right child. In the pass-by order, first look at the left child, then the parent, and finally the right child. In the return order, first look at the left child, then the right child, and finally the parent. The search is realized by recursively applying these algorithms in order from the root.

Now, let's create a program that outputs node data according to these. For simplicity, consider a binary tree that does not have an empty element when using an array of length 7.

Implementation example

C++

BinaryTree.cpp

#include <iostream>
using namespace std;

void breadthFirstSearch(string binaryTree[], int nodeNum);
void preorder(string binaryTree[], int nodeNum, int nodeIndex);
void inorder(string binaryTree[], int nodeNum, int nodeIndex);
void postorder(string binaryTree[], int nodeNum, int nodeIndex);

void breadthFirstSearch(string binaryTree[], int nodeNum)
{
  for (int i = 0; i < nodeNum; i++) {
    cout << binaryTree[i] + " ";
  }
  cout << endl;
}

void preorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  cout << binaryTree[nodeIndex] + " ";
  preorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  preorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
}

void inorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  inorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  cout << binaryTree[nodeIndex] + " ";
  inorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
}

void postorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  postorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  postorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
  cout << binaryTree[nodeIndex] + " ";
}


int main()
{
  string binaryTree[7] = {"President", "Design manager", "Engineer manager", "Character designer",
                          "UI designer", "Server engineer", "Infrastructure engineer"};

  breadthFirstSearch(binaryTree, 7);

  preorder(binaryTree, 7, 0);
  cout << endl;
  inorder(binaryTree, 7, 0);
  cout << endl;
  postorder(binaryTree, 7, 0);
  cout << endl;
}

Java

BinaryTree.java

public class BinaryTree {
	public static void breadthFirstSearch(String[] binaryTree, int nodeNum) {
		for (int i = 0; i < nodeNum; i++) {
			System.out.print(binaryTree[i] + " ");
		}
		System.out.println("");
	}

	public static void preorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		System.out.print(binaryTree[nodeIndex] + " ");
		preorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		preorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
	}

	public static void inorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		inorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		System.out.print(binaryTree[nodeIndex] + " ");
		inorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
	}

	public static void postorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		postorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		postorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
		System.out.print(binaryTree[nodeIndex] + " ");
	}

	public static void main(String[] args) {
		String[] binaryTree = {"President", "Design manager", "Engineer manager", "Character designer",
													 "UI designer", "Server engineer", "Infrastructure engineer"};

		breadthFirstSearch(binaryTree, 7);

		preorder(binaryTree, 7, 0);
		System.out.println();
		inorder(binaryTree, 7, 0);
		System.out.println();
		postorder(binaryTree, 7, 0);
		System.out.println();

	}
}

Explanation about implementation

Breadth-first search when a binary tree is realized using an array is easy because it only reads the array in order from the beginning. In the case of the destination order, it is realized by recursing by giving the index of the node currently being viewed to the argument nodeIndex. Since the order of passing and returning is different, it can be achieved by simply replacing the lines in the order of passing. The idea of recursion is difficult, but if you are a beginner, think slowly about what this program means. The execution results are as follows.

President Design Department Manager Engineer Department Manager Character Designer UI Designer Server Engineer Infrastructure Engineer
President Design Department Manager Character Designer UI Designer Engineer Department Manager Server Engineer Infrastructure Engineer
Character Designer Design Department Manager UI Designer President Server Engineer Engineer Department Manager Infrastructure Engineer
Character Designer UI Designer General Manager of Design Department Server Engineer Infrastructure Engineer General Manager of Engineer Department President

Did you understand the search for binary trees?

Part 3 is here