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

What this article shares with you is about how to analyze the binary tree in the basis of the data structure. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Let's take a look at it with the editor.

one。 The basic knowledge of binary tree

Basic concept

The top point of a tree is called the root node. if multiple nodes are connected under a node, then the node is called the parent node, and the lower node is called the child node. Each node of the binary tree has at most two child nodes. The number of child nodes of a node is called degrees, and the degree of each node of the binary tree can only be one of the 0 degrees, and the nodes with degree 0 are called leaf nodes.

Basic characteristics

Binary search tree is a special binary tree, which inserts and deletes very efficiently.

two。 Basic exercise

Implement binary search tree (BST)

The logic of TIP:BST when inserting data is itself a kind of dichotomy thinking.

Traversal of trees

TIP: tree traversal is generally divided into preorder traversal, mid-order traversal, and post-order traversal, where order refers to the access order for a node and its left and right child nodes. Specific examples of use scenarios include: first order traversal time, which can be used to view the tree structure, medium order traversal, which can be used to display sorting results, and post order traversal, which can be used to calculate the data size occupied by files in the directory.

Lookup of values

3.1 find a given value

TIP: it's actually dichotomy search.

3.2 find the minimum

The leftmost node in TIP:BST.

3.3 find maximum

The rightmost node in the TIP:BST.

Delete nod

TIP: mainly pay attention to the logic when deleting nodes that also contain left and right child nodes. The rules inserted by BST show that all nodes in the right subtree of the node are greater than the current node value, so the minimum value found in the right subtree is greater than all the values on the left subtree of the current node, so floating it to the current position of the node to be deleted does not affect the binary tree characteristics.

Count

three。 After-class exercises (Section 10 exercises in the book)

Add a new method to BST to return the number of nodes in BST.

Add a new method to BST to return the number of edges in BST.

Add a new method max () to the BST class, which returns the maximum value.

Add a new method min () to the BST class, which returns the minimum value.

Write a program, read into a large text file, and save the words in the BST to show the number of times each word appears

four。 Exercise train of thought

Add a count attribute to the BST constructor and modify the count value to achieve the count when the nodes are added or deleted successfully.

The number of BST edges is 1. 5 less than the number of nodes.

(slightly)

(slightly)

The decomposed words are actually strings. In fact, the comparison of strings is to compare ASCII codes one by one from the first bit. Just use the BST implemented above to do exercises. Word frequency statistics are more likely to use Trie trees, that is, dictionary trees, which can be checked by interested readers.

five。 Restore binary tree according to ergodic order

[preorder + middle order] or [post order + middle order] can restore a unique binary tree, but the binary tree restored according to [preorder + postorder] is not unique (if you are interested, you can take a look at this article, "Why only preorder and postorder are given. You can't only determine a binary tree"). The binary tree here refers to the general binary tree, not the binary search tree. Or there are many related articles, and it is not difficult to understand "restoring the binary tree structure by traversing sequence" with a graph, so it is also recommended to code and implement it.

six。 On binary trees

Binary tree is a very important data structure, the book introduces only the most basic knowledge, further learning will involve the mathematical characteristics of binary tree, limit more performance and better balanced binary tree, full binary tree, red-black tree and so on. And related depth-first and breadth-first algorithms.

The above is how to parse the binary tree in the basis of the data structure. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

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.