Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
M-ary tree
Summary
In graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary or k-way tree) is an arborescence (or, for some authors, an ordered tree) in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three.
A full m-ary tree is an m-ary tree where within each level every node has 0 or m children.
A complete m-ary tree (or, less commonly, a perfect m-ary tree) is a full m-ary tree in which all leaf nodes are at the same depth.
For an m-ary tree with height h, the upper bound for the maximum number of leaves is .
The height h of an m-ary tree does not include the root node, with a tree containing only a root node having a height of 0.
The height of a tree is equal to the maximum depth D of any node in the tree.
The total number of nodes in a perfect m-ary tree is , while the height h is
By the definition of Big-Ω, the maximum depth
The height of a complete m-ary tree with n nodes is .
The total number of possible m-ary tree with n nodes is (which is a Catalan number).
tree traversal
Traversing a m-ary tree is very similar to traversing a binary tree. The pre-order traversal goes to parent, left subtree and the right subtree, and for traversing post-order it goes by left subtree, right subtree, and parent node. For traversing in-order, since there are more than two children per node for m > 2, one must define the notion of left and right subtrees. One common method to establish left/right subtrees is to divide the list of children nodes into two groups. By defining an order on the m children of a node, the first nodes would constitute the left subtree and nodes would constitute the right subtree.
Using an array for representing a m-ary tree is inefficient, because most of the nodes in practical applications contain less than m children. As a result, this fact leads to a sparse array with large unused space in the memory.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.