“This is my fifth day of the November Gwen Challenge.The final text challenge in 2021”

Abstract

Binary tree is the most basic and important structure in tree structure. There are many different types of binary trees derived from binary trees. After learning the different derivative structures of binary trees, we will find that they cannot escape the definition and specificity of binary trees.

Tree structure

There are many scenarios of tree structure in life, such as the organizational structure of the company, files and directories, and so on. The tree structure is used for efficiency purposes.

The basic concept

The tree has node, root node, parent node, child node, brother node these several keywords. A tree can have no node, called an empty tree, or it can have only one node, the root node. Trees can also be subtrees, left subtrees, and right subtrees.

In the structure of the tree, there are the following:

  • Degree of nodes: the number of subtrees
  • Degree of tree: the maximum degree of all nodes
  • Leaf node: node with degree 9
  • Non-leaf node: a node whose degree is not 0
  • Number of layers: The root node is at layer 0, the children of the root node are at layer 2, and so on until the end
  • Depth of nodes: The total number of nodes on a unique path from the root node to the current node
  • Node height: The total number of nodes along the path from the current node to the farthest leaf node
  • Tree depth: the maximum depth of all nodes
  • Tree height: The maximum of all node heights
  • The depth of the tree is equal to the height of the tree

The type of tree

Trees are divided into ordered trees, disordered trees and forests. There is a sequential relationship between the children of any node in an ordered tree, but there is no sequential relationship between the children of any node in an unordered tree, and the forest is a collection of many disjoint trees.

Binary Tree

A binary tree is a tree with a maximum degree of 2 per node (with a maximum of 2 subtrees), and the left and right subtrees of the binary tree have order. Even if a node has only one subtree, the left and right subtrees need to be distinguished.

The nature of the

Binary trees have the following characteristics:

  • The i-th layer of a nonempty binary tree with at most 2^(i-1) nodes (I >= 1)

  • At most 2^ h-1 nodes in a binary tree of height H (h >= 1)

  • For any non-empty binary tree, if the number of leaf nodes is N0 and the number of nodes with degree 2 is N2, then n0 = n2 + 1

    • Assuming that the number of nodes with degree 1 is N1, then the total number of nodes in the binary tree is n = N0 + N1 + n2
    • The number of edges of the binary tree T = n1 + 2 * n2 = n-1 = N0 + N1 + n2-1
    • N0 = n2 + 1

The type of binary tree

  • True binary tree: The degree of all nodes is either 0 or 2
  • Full binary tree: All nodes have a degree of either 0 or 2. And all the leaf nodes are in the last layer
  • Complete binary tree: only the last 2 layers of leaves appear, and the last 1 layer of leaves are aligned to the left

It can be concluded from above that full binary tree must be true binary tree, but true binary tree is not necessarily full binary tree

implementation

According to the characteristics of binary tree, it can be concluded that each node has a parent node, a left child node, a right child node, and elements of its own node. Check whether the left and right child nodes are empty to determine whether the node is a leaf node or a node with degree 2. The code is as follows:

Static class Node<E> {// parent Node<E> parent; // Node<E> left; // right child Node<E> right; // element E element; public Node(E element, Node<E> parent) { this.element = element; this.parent = parent; Public Boolean isLeaf() {return left == null && right;} public Boolean isLeaf() {return left == null && right == null; } @return */ public Boolean isHaveTowChildren() {return left! = null && right ! = null; }}Copy the code