Shulou(Shulou.com)06/03 Report--

Today, I will talk to you about how to implement the binary tree traversal algorithm in the data structure, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

Today we look at a new data structure, tree.

Outline of this article

Outline of this article

Note: some students may not like mobile phone reading, so synchronize this article in my warehouse, you can go to Github to read, click on the bottom of the article to read the original text

Tree

Let's first take a look at Baidu encyclopedia's definition of tree.

A tree is a finite set of n (n > = 0) nodes. When n = 0, we call it empty tree, and empty tree is a special case of tree.

In any non-empty tree:

A node that has one and only one specific node called Root

When n > 1, the other nodes can be divided into m (m > 0) disjoint finite sets T1, T2, .TM, in which each set itself is a tree and is called a subtree of the root.

Let's unravel the above two sentences together, what on earth is a subtree? See the picture below

Tree

For example, in the figure above

There is and only one specific node is called the root node, which is the orange node in the image above.

When the number of nodes is greater than 1, the nodes except the root node can be divided into m disjoint finite sets T _ 1 ~ T _ 2. TM.

For example, in the image above, we divide the nodes other than the root node into two finite sets: T1 (2magin3, 4, 5, 6, 7) and T2 (8, 9).

Then T1 (green node) and T2 (blue node) are subtrees of the root node (orange node).

After we took it apart, we found that the example in our picture above meets the requirements of the tree, and I don't know if you have noticed this place.

Nodes other than root nodes can be divided into m disjoint finite sets.

So what is the meaning of this disjoint? See the picture below.

We substitute (A), (B), (C), (D) into the above definition and find that (A), (B) conforms to the definition of tree, and (C), (D) does not match, because (C), (D) they all have intersecting subtrees.

Well, now that we know how to identify trees, let's take a closer look at trees through the following two pictures.

It mainly starts from the node type and the relationship between nodes.

The height and depth of the nodes here

It may be easy to get confused, so let's just put it into reality.

When we find the depth of an object, we measure it from the top down, and when we find the height, we measure it from the bottom up, so is the height and depth of the node.

Binary tree

What we encounter when doing exercises is the binary tree. Let's take a look at the binary tree.

The premise of a binary tree is that a tree, that is, it needs to meet the definition of our tree, but also needs to meet the following requirements

Each node has at most two child nodes, the left child node and the right child node.

Note that we mention the most here, so the binary tree does not have to require each node to have two child nodes, some have only one left child node, and some nodes have only one right child node.

Let's summarize the characteristics of binary tree.

Each node has at most two subtrees, that is to say, there are no nodes with a degree greater than 2 in the binary tree, and the degree of the node can be 0 ~ 1 ~ 2.

The left subtree and the right subtree are in order and can be divided into left and right.

If there is only one subtree, distinguish whether it is a left subtree or a right subtree

Well, we have understood the characteristics of binary tree, so let's analyze whether the tree in the following figure meets the definition of binary tree. There are several kinds of binary tree.

The above picture shows five different binary trees. In the definition of binary trees, it is mentioned that the left and right subtrees of binary trees are in order, so Bline C is two different binary trees, so the picture above shows five different binary trees.

Special binary tree

Let's talk about some special binary trees, which can help us take into account the special circumstances when doing exercises.

Full binary tree

Full binary tree: in a binary tree, all branch nodes have left and right subtrees, and all leaves are on the same layer. See the picture below

We find that only (B) meets the definition of full binary tree, and we find that full binary tree is also a kind of complete binary tree.

Complete binary tree

Complete binary tree: leaf nodes can only appear in the lowest and lower layers, and the lowest leaf nodes are concentrated in the left part of the tree.

Oh! We can understand that except for the last layer, the number of nodes in the other layers is full, and the leaf nodes in the last layer must be left.

Let's take a look at these examples.

In the above examples, (A) (B) is a complete binary tree, and (C) (D) is not a complete binary tree.

Oblique binary tree

This is easy to understand. An oblique binary tree is an oblique binary tree. All nodes are called left oblique trees with only left subtrees, and all nodes with right subtrees are called right oblique trees.

No, these are the following two.

In addition, there are some properties of the binary tree, such as the number of nodes at most in the first layer, the node with a degree of 2 through the leaf node, the depth of the binary tree through the node tree, and so on. These are the knowledge of the postgraduate entrance examination, so we will not repeat them here. Students in need can take a look at the data structure of Wang Dao or Tianqin, which is described in detail and is accompanied by a proof process.

Well, we have learned about binary trees, so how to store binary trees?

How to store a binary tree

Binary trees are often stored in two ways: array-based sequential storage and pointer-based binary chain storage.

Here we review how to store a complete binary tree in an array.

First of all, let's look at the root node, that is, the node with a value of 1, which has an index of 1 in the array, and its left child node, that is, the node with value 4, has an index of 2, and the right child node is a node with a value of 2. Its index is 3.

Did we find the relationship?

In the array, if the subscript of a node (non-leaf node) is I, then its left child node is indexed as 2sigi (here you can get the left child directly by multiplication, which is why the first position is vacated, and if you save from 0, you need 2i+1), the right child node is 2i+1, and its parent node is iLever 2. Since we can find the left and right child nodes of a node according to the index, we have no problem storing it in an array.

But let's consider this scenario again. What happens if we use an array to store diagonal trees?

If the left child node is stored through 2pragi, a lot of storage space will be wasted if the oblique tree is encountered, which is obviously not appropriate.

Therefore, when storing a complete binary tree, we use array storage, which is undoubtedly the most memory-saving, but it is not appropriate to store oblique trees.

So let's introduce another storage structure, chain storage structure.

Since each node of the binary tree has at most two children, we only need to define one data field and two pointer fields for each node.

Val is the value of the node, left points to the left child node, and right points to the right child node.

Let's use the chained storage structure for tree 1, 2, 3, 4, 5, 6, 7, which is the case below.

The node structure definition code of binary list public class BinaryTree {int val; BinaryTree left; BinaryTree right; BinaryTree () {} BinaryTree (int val) {this.val = val;} BinaryTree (int val, BinaryTree left, BinaryTree right) {this.val = val; this.left = left; this.right = right;}}

In addition, when we do exercises, we can realize the data structure by ourselves, deepen our understanding, improve our basic skills, and take more and more interviews.

All right, let's talk about traversing the tree.

Below, I will describe it in the form of a dynamic diagram, which is easy to understand. I will also summarize the corresponding topics for you. Welcome to read.

Traversing binary tree

The traversal of binary tree means that starting from the root node, all the nodes of the binary tree are accessed in a certain order, so that each node is visited and visited once.

Here we introduce several traversal methods of binary tree and their corresponding topics, pre-order traversal, middle order traversal, post-sequence traversal, sequence traversal.

Preorder traversal

The order of preorder traversal is that for a node in the tree, first traverse the node, then traverse its left subtree, and finally traverse its right subtree.

Just looking at the text is a little stiff. Let's just look at the animation.

Preorder traversal

Test question: leetcode 144. Preorder traversal of binary tree

Code implementation (recursive version)

Class Solution {public List preorderTraversal (TreeNode root) {List arr = new ArrayList (); preorder (root,arr); return arr;} public void preorder (TreeNode root,List arr) {if (root = = null) {return;} arr.add (root.val); preorder (root.left,arr); preorder (root.right,arr) }}

Time complexity: O (n) space complexity: O (n) is the stack cost in the recursive process, with an average of O (logn), but O (n) when the binary tree is an oblique tree.

In order to control the length of the article, the iterative traversal form of the binary tree will be introduced in the next article.

Mid-order traversal

The order of traversal in the middle order is that for a node in the tree, first traverse the left subtree of the node, then traverse the node, and finally traverse its right subtree

Continue to watch the animation, if some forget or just learn the data structure of the students can simulate their own implementation steps.

Mid-order traversal

Test question: leetcode 94 middle order traversal of binary tree

Code implementation (recursive version)

Class Solution {public List inorderTraversal (TreeNode root) {List res = new ArrayList (); inorder (root, res); return res;} public void inorder (TreeNode root, List res) {if (root = = null) {return;} inorder (root.left, res); res.add (root.val) Inorder (root.right, res);}}

Time complexity: O (n) space complexity: O (n)

Post-order traversal

The order of traversal is that for a node in the tree, first traverse the left subtree of the node, then traverse the right subtree, and finally traverse the node.

Haha, continue to watch the animation, after watching the animation will understand.

Post-order traversal

Test question: leetcode 145. post-order traversal of binary tree

Code implementation (recursive version)

Class Solution {public List postorderTraversal (TreeNode root) {List res = new ArrayList (); postorder (root,res); return res;} public void postorder (TreeNode root, List res) {if (root = = null) {return;} postorder (root.left, res); postorder (root.right, res); res.add (root.val) }}

Time complexity: O (n) space complexity: O (n)

Sequence traversal

As the name implies, it traverses layer by layer.

For example, the sequence traversal sequence of the binary tree is 1 ~ 9.

The sequence of the binary tree, here we need to use other data structures to achieve, we think, we need to traverse the binary tree hierarchically, traversing from top to bottom, what data structure can we use to help us?

We can take advantage of the first-in-first-out (FIFO) feature of the queue and use the queue to help us complete sequence traversal, as follows

Let each layer of the binary tree join the team, and then perform the dequeue operation in turn.

When performing the dequeue operation on this layer node, you need to queue up the left child node and the right child node of the node.

In this way, when all the nodes on this layer are out of the team, the next layer will join the team.

But what we need to consider is that we need a variable to hold the number of nodes in each layer.

This is done to prevent the dequeue operation from being performed all the time, so that the output cannot be layered.

All right, let's go straight to the animation.

Test topic: sequence traversal of leetcode 102binary tree

Title code

Class Solution {public List levelOrder (TreeNode root) {List res = new ArrayList (); if (root = = null) {return res;} / / join the root node, that is, the first layer Queue queue = new LinkedList (); queue.offer (root); while (! queue.isEmpty ()) {List list = new ArrayList () Int size = queue.size (); for (int I = 0; I < size; + + I) {TreeNode temp = queue.poll (); / / if the child node is not empty, join the queue if (temp.left! = null) queue.offer (temp.left); if (temp.right! = null) queue.offer (temp.right) List.add (temp.val);} res.add (list);} return res;}}

Time complexity: O (n) space complexity: O (n)

If you have thoroughly learned the sequence traversal of the binary tree, you can easily solve the following problems with the same train of thought, without even turning a corner.

Leetcode 107. Sequence traversal of binary tree through II

Leetcode 103. Sawtooth sequence traversal of binary tree

The above two questions are just overturned.

Leetcode 199. The right view of the binary tree

Leetcode 515. Find the maximum value in each tree row

Leetcode 637. Layer average of binary tree

These three questions are just some operations that have been added one layer.

Leetcode 116padding the next right side of each node

Leetcode 117 fills the next right 2 of each node

The two questions can be linked to the nodes on each level, and the codes of the two questions are the same.

After reading the above, do you have any further understanding of how to implement the binary tree traversal algorithm in the data structure? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.