This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

preface

  • I believe that you can’t get away from a course called data structure in college. At that time when learning data structure by C++ binary tree, linked list and other data structure of the whole giddy plug fart.
  • Today we are going to learn about binary trees

Binary tree

  • Binary trees are divided into full binary trees and complete binary trees.
  • Full binary tree: A binary tree in which all root nodes have left and right children. And all the leaf nodes are in the same layer. Such a binary tree is called a full binary tree. This binary tree is also aesthetically pleasing
  • Complete binary tree: The node numbered I is in the same position as the element numbered I in the full binary tree of the same depth.

features

  • I summarize the following features about binary trees:

  • There are at most 2 to the I minus 1 nodes at the I th level of the binary tree

  • A binary tree of depth K has at most 2^ K -1 nodes and at least K nodes

  • In the binary tree, if the number of nodes of leaf is N0 and the number of nodes of degree =2 is n2, then n0=1+n2;

  • A complete binary tree with n nodes has a depth of log2n +1

  • Nodes in a complete binary tree with N nodes are numbered according to layers starting from 1, and any node numbered as I is as follows:

    @1. If I >1, the parent number of node I is [I /2]; otherwise, node I is the root node and has no parent; @2. If 2i<=n, the number of the left child of node I is 2i; otherwise, there is no left child. @3. If 2i+1<=n, the number of the right child of node I is 2i+1, otherwise there is no right child.Copy the code

traverse

  • Preorder traversal: root -> left -> right

  • Middle order traversal: left -> root -> right

  • After traversal: left -> right -> root

  • Sequential traversal: Traversal from top to bottom and from left to right in each layer.

conclusion

  • Binary tree is actually a kind of deformation of divide-and-conquer, middle order traversal in binary tree is a kind of ordered data arrangement. We also often use this feature to sort data. Another binary is a flexible data structure. It is more space-efficient in construction. In the search is also very high efficiency. Binary trees are also widely used in practice. Pay attention to me. Find out more next time!!