Basic Concepts of Trees

A tree is a data structure composed of nodes or vertices and edges (possibly nonlinear) that does not contain any cycles. A tree without nodes is called an empty (null or empty) tree. A non-empty tree includes a root node and (likely) multiple additional nodes, all nodes forming a multi-level hierarchical structure.

A tree is a special type of graph (graphs will be mentioned in subsequent articles).

Prefix Tree (Trie)

Directed Tree

Its edges have direction. And a tree is a connected graph without simple cycles.

The number of edges starting from node v is called v’s out-degree. The number of edges ending at v is called v’s in-degree. In the figure above, node v2’s in-degree is 1, out-degree is 2.

Cycles and Connectivity

Height and Nodes

Binary Tree

Binary trees are further divided into: perfect binary tree, complete binary tree, full binary tree

Perfect Binary Tree (Full Binary Tree)

Every node except leaf nodes has two child nodes, every level (including the last level) is completely filled

Complete Binary Tree

A complete binary tree satisfies perfect binary tree from root node to second-to-last level, the last level can be incompletely filled, its leaf nodes are all left-aligned

Full Binary Tree

All non-leaf nodes have degree 2 In other words: as long as you have children, you must have two children.

Article Link: