This is the 24th day of my participation in the August Text Challenge.More challenges in August”

Properties of binary trees

If the number of levels of the root node is 1, a non-empty binary tree has at most 2^(i-1) nodes at the i-th level.

If the number of layers of the root node is 1, the maximum number of nodes in a binary tree of depth h is 2^ H-1.

For any binary tree, if the number of leaf nodes of degree 0 is N0 and the number of branch nodes of degree 2 is n2, then n0 = n2+1

If the number of layers of the root node is 1, h=Log2(n+1). (ps: Log2(n+1) is log base 2, n+1 is logarithm)

For a complete binary tree with N nodes, if all nodes are numbered from 0 according to the array order from top to bottom and left to right, then for the node with serial number I:

  1. If I >0, the parent serial number of the node at position I :(i-1)/2; I =0, I is the number of the root node, there is no parent node
  2. If 2i+1 is less than n, the serial number of the left child is: 2i+1, 2i+1>=n otherwise, there is no left child
  3. If 2i+2 is less than n, the number of the right child: 2i+2, 2I +2>= N Otherwise, there is no right child

Sequential storage of binary trees

1. Sequential storage of binary tree concepts

The sequential storage of binary tree is to store the node elements in binary tree by a group of continuous storage units (array). Generally, the nodes of binary tree are stored in the order from top to bottom and from left to right.

Sequential storage binary tree features:

1. Sequential binary trees usually consider only complete binary trees

The left child of the NTH element is 2*n+1

The right child of the NTH element is 2*n+2

4. The parent of the NTH element is (n-1) /2

5. N indicates the number of elements in the binary tree, starting from 0

2. Sequential storage binary tree traversal

Public Class ArraysBinaryTree {private int[] ArraysBinaryTree; public ArraysBinaryTree(int[] arrays){ this.arrays = arrays; } / * * * sequence before storing binary tree traversal * @ param index * / public void preOrder (int index) {if (this. Arrays = = null | | arrays. The length = = 0) { System.out.println(" array is empty, cannot be traversed "); Left recursion} / * * * * / if ((index * 2 + 1) < arrays. Length) {preOrder (index * 2 + 1); } / * * * recursion * / if (to the right (index * 2 + 2) < arrays. Length) {preOrder (index * 2 + 2); }}}Copy the code

 Cue binary tree

Build the sequence [1,3,6,8,10,14] into a binary tree

Problem analysis:

1. When we perform middle-order traversal on the above binary tree, the numbers are listed as [8,3,10,1,6,14]

The left and right Pointers to nodes 2, 6,8,10, and 14 are not well used.

3. How to solve the problem if we can make full use of the left and right Pointers to each node

Cue binary trees are the only option

1. Cue binary tree introduction

The binary tree that adds clues to the nodes of the binary tree is called the cued binary tree, and the process of traversing the binary tree in a certain way (such as pre-order, mid-order, post-order, etc.) to make it become a cued binary tree is called the cuing of the binary tree

For the binary tree with N nodes, there are N +1 empty chain fields in the binary chain storage structure. These empty chain fields are used to store the Pointers of the precursor nodes and successor nodes of the node in a certain traversal order. These Pointers are called clues, and the binary tree with clues is called clue binary tree.

A Threaded binary list is called a Threaded BinaryTree, and the corresponding BinaryTree is called a Threaded BinaryTree. According to the different nature of cue, the binary tree of cue can be divided into three kinds: the binary tree of preorder cue, the binary tree of middle order cue and the binary tree of postorder cue.

The node before a node is called a precursor node, and the node after a node is called a successor node.

2. Traversal of binary tree chain structure

Traversal means that each node in the tree is visited once and only once along a search route. What you do to access a node depends on the application problem. Ergodic operation is one of the most important operations in binary tree, and it is the basis of other operations in binary tree. Recursive structure traversal before/middle/after: is named according to the location of the access node operation

  • NLR: Preorder Traversal – access to the root node takes place before traversing its left and right subtrees.
  • LNR: Inorder Traversal – access to the root occurs between traversing its left and right subtrees.
  • LRN: Postorder Traversal — access to the root occurs after traversing its left and right subtrees.

The Node to be accessed must be the root of a subtree, so N(Node), L(Left subtree), and R(Right subtree) can be interpreted as the root, the Left subtree of the root, and the Right subtree of the root. NLR, LNR and LRN are also known as pre-root traversal, mid-root traversal and post-root traversal respectively.

Order traversal: In addition to the first order traversal, middle order traversal, after order traversal, also can carry on the order traversal of binary tree. A binary tree root node of the layer number is 1, sequence traversal is from the root node of a binary tree, the first layer of first visit the root node, and then from left to right to access node of the layer 2, followed by the third layer nodes, and so on, from top to bottom, from left to right step by step the process of access to the tree node is sequence traversal.