Felial-heir chains -> 3-ary trees, theorems
Budget: £10 – £20 GBP
Filial-heir chains, also known as left-child-right-sibling (LCRS) trees and doubly chained trees (Sussenguth, 1963), are rooted binary trees that can be used to represent k-ary trees (also known as k-way trees) in which k > 2.
Come up with a set of 10 theorems that describe the structure of filial-heir chains in relation to their equivalent k-ary tree. In particular, present theorems that predict metrics of interest following forward and reverse Knuth transforms (i.e., the process of converting a k-ary tree into a filial-heir chain and vice versa).
Metrics of interest that can be used, but are not limited to: numbers of edges, nodes, leaf nodes, and interior nodes; tree height and balance, number of null pointers; maximum, minimum and average number of nodes in each level, and diameter (sometimes known as width).
Come up with a set of 10 theorems that describe the structure of filial-heir chains in relation to their equivalent k-ary tree. In particular, present theorems that predict metrics of interest following forward and reverse Knuth transforms (i.e., the process of converting a k-ary tree into a filial-heir chain and vice versa).
Metrics of interest that can be used, but are not limited to: numbers of edges, nodes, leaf nodes, and interior nodes; tree height and balance, number of null pointers; maximum, minimum and average number of nodes in each level, and diameter (sometimes known as width).