tree

• A rooted tree is a tree in which one node has been designated the root.
• Every edge is directed away from the root.
• Given a vertex 𝑣 in a rooted tree 𝑇:
  • Parent: unique vertex 𝑢 such that (𝑢, 𝑣) is an edge (in the direction from root to 𝑣)
  • Child: any vertex for which 𝑣 is a parent
  • Siblings : vertices with the same parent
  • Ancestors : all vertices from root to 𝑣 (except itself)
  • Descendants : vertices with 𝑣 as an ancestors
• A vertex of a tree is called a leaf if it has no children.
• Vertices that have children are called internal vertices.

Rooted Trees（有根树）是一种基础的数据结构，它由若干个节点和连接这些节点的边组成。它们通常用于表示层次结构，例如文件系统、网站导航、家谱等。根据定义，每个树都有一个根节点，它是唯一的，并且没有父节点。每个节点可以有零个或多个子节点，每个子节点都连接到其父节点。树的节点可以表示任何对象，可以是简单的值（例如数字或字符串），也可以是更复杂的对象或数据结构。节点可以具有任意数量的子节点，但每个节点最多只能有一个父节点。

• A Game (State) Tree models the different possible outcomes in a game.
  • Vertices: positions (states) in a game.
  • Edges: legal moves from one position (state) to another.
  • Leaves: Final positions (states) of a game.
• eg: Tic-Tac-Toe

• A rooted tree is called 𝑚-ary if every internal vertex has no more than 𝑚 children (maximum is 𝑚).
• It is called full if every internal (non-leaf) vertex has exactly 𝑚 children.
• A 2-ary tree is called a binary tree. If 𝑣 is an internal vertex of a binary tree, it has at most two children. The first we call the left child and the second the right child.
• If vertex 𝑣 is in a tree 𝑇, the sub-tree with root 𝑣 is the tree consisting of 𝑣 and all its descendants.

m-ary Tree是一种树形数据结构，它的每个节点最多有m个子节点。m通常被称为树的度。当m=2时，m-ary Tree就是二叉树；当m=3时，m-ary Tree就是三叉树。m-ary Tree常用于计算机科学中的搜索和排序算法，例如B树和B+树，它们被广泛应用于数据库和文件系统的实现中。在m-ary Tree中，节点的度数可以任意，而不像二叉树那样只能是2，因此m-ary Tree可以更灵活地表达数据结构和算法的特点。

The level of a node is the length of the path from the root to the node (The level of the root is defined to be zero).

• The height of a tree is maximum level of node.
• A rooted m-ary tree with height ℎ is called balanced if all leaves are at levels ℎ or ℎ − 1.