This is the fifth day of my participation in Gwen Challenge

Linear structure

Binary tree structure

At most two forks. If there are three or more, it is called a multi-fork tree

The tree structure of life

Using a tree structure is a great way to be more efficient and important in an interview.

Basic concepts of trees

Node, root node, parent node, child node, sibling node

  • Nodes: 1, 2, 3, 4…
  • Root node: 1
  • Parent node: 1 is the parent node of 2, 3, 4, 5, and 6, and 2 is the parent node of 21 and 22
  • Sibling nodes: 2, 3, 4, 5, and 6 are siblings of each other

A tree can have no nodes, called an empty tree.

A tree can have only one node, which is the root node.

Subtree: For example, 2-21 is a subtree

Left subtree right subtree: 21 is the left subtree of 2, 22 is the right subtree of 2

** Node degree: ** number of subtrees. The degree of 2 is 2, the degree of 6 is 1, the degree of 61 is 0

** Tree degree: ** the largest value of all node degrees. The maximum degree in the figure is 5, which is the degree of 1.

** leaf node: node with ** degree 0

** non-leaf node: a node whose ** degree is not 0

** Layers: ** the root node is at layer 1, and the children of the node are at layer 2, and so on

Depth of nodes: The total number of nodes on a unique path from the root node to the current node. The depth of 2 is 2 and the depth of 31 is 3

Node height: The total number of nodes on the path from the current node to the farthest leaf node. The height of 2 is 3

** Tree depth: ** maximum depth of all nodes, graph depth is 4

** Tree height: ** The maximum height of all nodes, graph height is 4

The depth of the tree is equal to the height of the tree

Ordered tree, disorder tree, forest

Ordered tree: A tree in which the children of any node are sequentially related

Unordered tree: There is no sequential relationship between the children of any node in the tree

Forest: A collection of M mutually exclusive trees

Binary tree

  • Each node has a maximum degree of 2 (at most 2 subtrees)

  • Left and right subtrees are ordered

  • Even if a node has only one subtree, distinguish between the left and right subtrees

Binary trees are ordered trees because the left and right subtrees are strictly separated.

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, how to deduce?

  • Assume that the number of nodes with degree 1 is N1, then the total number of nodes in the binary treen = n0 + n1 + n2
  • The number of edges in a binary treeT = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 -1

Binary tree

All nodes have degrees of either 0 or 2

Full binary tree

All nodes have degrees of either 0 or 2. And all the leaf nodes are in the last layer.

In the same height of the binary tree, the full binary tree has the largest number of leaves and total nodes

A full binary tree is always a true binary tree, and a true binary tree is not always a full binary tree.

Assume the height of the full binary tree is h(h>=1)

  • Number of nodes at layer I:2^(i-1)
  • Number of leaf nodes:2^(h-1)
  • The total nodes:2^h-1

Complete binary tree

The leaf nodes only appear in the last 2 layers, and the leaf nodes in the last 1 layer are aligned to the left.

To put it more simply: complete binary trees are arranged from top to bottom, left to right

A complete binary tree is a full binary tree from the root node to the penultimate level 2.

A full binary tree is always a complete binary tree, and a complete binary tree is not always a full binary tree.

The nature of the

  • Nodes of degree 1 -> have only left subtrees

  • There are either one or zero nodes of degree 1

  • A complete binary tree with the same number of nodes has the smallest height

  • Assuming that the height of the complete binary tree is H (h>=1), then

    • There are at least2^(h-1)A node
    • Up to a2^h -1A node
    • If the total number of nodes is N2^(h-1) <= n < 2^h.h-1 <= log2^n < h.h = floor(log2^n) + 1.floor()I’m going to round down,ceiling()It’s rounded up.

There are two other important properties of binary trees that we’ll use for binary heaps. The following figure

The interview questions

【 典 型 范 例 1 】