Tree structure
A tree structure is a data structure that expresses the hierarchical relationship
between elements. It is suitable for expressing relationships branched
between data.
node：Area for storing data.（Element part of the tree structure）
branch：Line connecting the node.（Connect elements）
root node：The first node without a parent node.
leaf node：Terminal node without a child node.
In addition, there are several types of tree structures, so I will introduce them.
（１）Binary tree
A binary tree is a tree that has two or less children in each node. Distinguish
the two children like the left child and the right child, respectively. The part
rooted on the left child is called the left subtree, and the part rooted on the
right child is called the right subtree. The figure below is an example of a
binary tree.
（２）Perfect binary tree
Among the binary trees, those with the same length of the route from the root
to the leaf are called a perfect binary tree. The figure below is an example of
a perfect binary tree.
（３）Binary search tree
Each node of the binary search tree has a key. The key values of all the nodes
of the left subtree are less than the key values of the parent, and the key
values of all the nodes of the right subtree are equal to or greater than the
parent. The relationship is "key value of left subtree ＜ key value of parent
≦ key value of right subtree".
（４）Heap
A heap is a perfect binary tree whose parent key value is always greater than
(or less than) the child key value.
（５）Multi-way tree
A multi-way tree has three or more children from each node.
[Japanese]
木構造（Tree）
木構造とは、要素同士の階層関係を表現するデータ構造です。データ間の分岐関係を表現するのに適しています。
節（ノード）：データを格納する領域です。（木構造の要素部分）
枝：節を結ぶ線です。（要素と要素をつなぐ）
根（ルート）：親の無い先頭の節です。
葉：子の無い末端の節です。
また、木構造にはいくつか種類がありますので、一部を紹介します。
（１）二分木（binary tree）
二分木は、各節の子の数が２つ以下の木であるものです。２つの子をそれぞれ左の子、右の子と区別します。また、左の子を根とする部分を左部分木、右の子を根とする部分を右部分木といいます。下図は二分木の例です。
（２）完全二分木
二分木のうち、根〜葉までの経路の長さが等しいものを、完全二分木といいます。下図が完全二分木の例です。
（３）二分探索木（binary search tree）
二分探索木は、各節がキーを持ちます。左部分木の全ての節のキー値は親の
キー値より小さく、右部分木の全ての節のキー値は親と等しいか、親よりも
大きい木のことです。
「左部分木のキー値 ＜ 親のキー値 ≦ 右部分木のキー値」の関係が成り立ちます。
（４）ヒープ（heap）
ヒープは、親のキー値が常に子のキー値よりも大きい（または小さい）完全二分木のことです。
（５）多分木（Multi-way tree）
多分木は、各節から出る子の数が３つ以上の木のことです。
