Creation of Java complete binary tree and analysis of four traversal methods

This paper describes the creation and four traversal methods of Java complete binary tree. Share with you for your reference, as follows:

There is a complete binary tree as follows:

The first sequence traversal result should be: 1 2 4 5 3 6 7 the middle sequence traversal result should be: 4 2 5 1 6 3 7 the second sequence traversal result should be: 4 5 2 6 7 3 1 the sequence traversal result should be: 1 2 3 4 5 6 7

The first order traversal, middle order traversal and second order traversal of binary trees are actually the same, and they all perform recursive operations.

Let me record the level traversal: the level traversal needs to use the queue. The first in the queue is out of the queue. Each out of the queue element checks whether there are left and right children, and if there are, they will be added to the queue. Due to the use of the first in first out principle of the queue, the level traversal is carried out.

The complete code (Java implementation) is recorded below, including several traversal methods:

Operation results:

Attachment: the difference between full binary tree and complete binary tree

Full binary tree refers to such a binary tree: except the last layer, all nodes on each layer have two child nodes. In the full binary tree, the number of nodes on each layer reaches the maximum, that is, there are 2k-1 nodes on the k layer of the full binary tree, and the full binary tree with depth m has 2m-1 nodes.

Complete binary tree refers to such a binary tree: except the last layer, the number of nodes on each layer reaches the maximum; On the last layer, only a few nodes on the right are missing.

For a complete binary tree, leaf nodes can only appear on the two largest levels: for any node, if the maximum level of the descendant node under the right branch is p, the maximum level of the descendant node under the left branch is either P or P + 1.

A complete binary tree has the following two properties:

Property 5: the depth of a complete binary tree with n nodes is [log2n] + 1.

Property 6: let the complete binary tree have n nodes. If you start from the root node and number the nodes with natural numbers 1, 2,..., n according to the hierarchy (each layer from left to right), the following conclusions are reached for the nodes numbered K (k = 1, 2,..., n):

① If k = 1, the node is the root node and has no parent node; If k > 1, the parent node number of this node is int (K / 2).

② If 2K ≤ n, the number of the left child node of the node numbered K is 2K; Otherwise, the node has no left child node (and obviously no right child node).

③ If 2K + 1 ≤ n, the number of the right child node of the node numbered K is 2K + 1; Otherwise, the node has no right child node.

A full binary tree must be a complete binary tree, and a complete binary tree is not necessarily a full binary tree.

For more information about Java algorithms, readers who are interested can see the topics on this site: Java data structure and algorithm tutorial, summary of Java DOM node operation skills, summary of java file and directory operation skills, and summary of Java cache operation skills