This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

1. Introduction

Have you ever seen a Christmas tree? In data structures, a tree is a data structure that looks like a tree

Before we begin, some concepts that must be grasped

Tip: A node has at most two child nodes, its number of edges must equal the number of nodes -1, and the tree does not contain loops

  1. Node: Each element in the tree can be called a node, and each circle in the figure above is a node
  2. Root node: The node at the top of the tree. Figure A shows the root node
  3. Parent node: As the name implies, the father node. For example, node A is the father of B and C
  4. Child nodes: In reverse, B and C in the figure above are the children of A
  5. Leaf nodes: nodes without child nodes. Dhfis in the figure above are leaf nodes
  6. Height of node: How many lines are contained in the longest path from this node to the leaf node
  7. Node depth: The number of connections from the root node to the node
  8. Number of layers of nodes: depth of nodes + 1
  9. Tree height: How many lines run from the root to the farthest leaf

This paper mainly introduces the classification and storage of binary tree


2. Classification of binary trees

There are several kinds of binary trees

  1. Full binary tree
  2. Complete binary tree
  3. Balanced binary trees

And from those three we have B trees, B+ trees and so on


1.1 Full binary tree

A binary tree is a full binary tree if it has a maximum number of nodes at each level


1.2 Complete binary trees

All but the last layer are full binary trees; The last layer can be full, or it can be a node that lacks a continuous number; A tree satisfying the first two conditions can be a binary tree

How do you understand that?

You can imagine a tree expanding from the root node to the right child node after the left child node is expanded, and to the next level after the left child node is expanded. Perfect binary trees have good regularity


1.3 Balanced binary trees

The common realization methods of balanced binary tree are red black tree, AVL tree, scapegoat tree, weighted balanced tree, stretch tree and so on

Compared with linked lists, binary trees often have a special relationship between parent and child nodes and brother nodes, which makes searching and modifying data in trees more convenient than linked lists

However, if the binary tree to a linked list, so that the tree has the excellent properties of it will be difficult to show, efficiency will be big discount, in order to avoid such a situation, we hope every parent has a son, for the son and son left to right as much as possible, are not more than one layer, which is balanced binary tree

3. Storage of binary trees

3.1 Chain storage

The chain storage of binary trees relies on each node to record a pointer to the location of the next node, so there is no need for continuous memory space

Each node is divided into data, a pointer to the left node, and a pointer to the right node. In Java, the left and right Pointers record reference objects


3.2 Sequential Storage

Sequential storage is the use of an array for storage. Each location in the array stores only the data of the node, but does not store Pointers to the left and right child nodes. The child nodes are indexed by the array subscript, like this:


4. To summarize

It is the forerunner of binary tree, and I hope you can have an understanding of binary tree after reading it, and then give a deeper interpretation