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 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 preorder(string binaryTree[], int nodeNum, int nodeIndex);
void inorder(string binaryTree[], int nodeNum, int nodeIndex);
void postorder(string binaryTree[], int nodeNum, int nodeIndex);

{
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 = {"President", "Design manager", "Engineer manager", "Character designer",
"UI designer", "Server engineer", "Infrastructure engineer"};

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"};

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

}
}
``````

``````President Design Department Manager Engineer Department Manager Character Designer UI Designer Server Engineer Infrastructure Engineer