This is the 24th day of my participation in Gwen Challenge

What is a tree

A tree, a tree in our data structure is an abstract model of hierarchical data. It’s like a real tree with branches, it’s like a family tree, or an organizational chart of a company, and so on.

It is composed of n(n>=1) finite nodes to form a set with hierarchical relations. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down.

The characteristics of the tree

  • Each node has zero or more child nodes;
  • A node without a parent is called the root node.
  • Each non-root node has one and only one parent;
  • In addition to the root node, each child node can be divided into multiple disjoint subtrees.

Attributes of nodes

  • Depth: The depth of a node depends on the number of ancestor nodes it has.

Height of the tree The height of the tree depends on the maximum depth of all nodes. A tree can also be broken down into levels. The root node is at layer 0, its children are at layer 1, and so on.

The types of trees

  • Unordered tree: A tree in which the children of any node have no sequential relationship is called an unordered tree, also known as a free tree.
  • Ordered tree: A tree in which the children of any node have a sequential relationship is called an ordered tree.
  • Binary tree: each nodemostA tree with two subtrees is called a binary tree.
  • Full binary tree: All nodes except leaf nodesBoth contain two subtreesIs called a full binary tree.
  • Complete binary tree: A complete binary tree is one in which all layers are full of nodes except the last one, and the last one is short of consecutive nodes to the right.
  • Huffman tree (Optimal binary tree) : The binary tree with the shortest weighted path is called a Huffman tree or optimal binary tree. Nodes with larger weights are closer to the root.

The term

  1. Path and path length: In a tree, the path between children or grandchildren that can be reached from one node. The number of branches in a path is called the path length. If the number of layers of the root node is set as 1, the length of the path from the root node to layer L node is L-1.
  2. Weight of nodes and weighted path length: If a node in the tree is assigned a value that has some meaning, the value is called the weight of the node. The weighted path length of a node is: the product of the length of the path from the root node to the node and the weight of the node.
  3. The weighted path length of a tree: The weighted path length of a tree is defined as the sum of the weighted path lengths of all leaf nodes, denoted as WPL.

To be continued…