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

This article introduces you how to analyze python binary tree, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Many beginners may be new to data structures. Here are some basic concepts about trees.

The definition of binary tree

A binary tree is a finite set of n (n > = 0) nodes, which is either an empty set (called an empty binary tree) or consists of a root node and two disjoint left and right subtrees called root nodes, respectively. The following figure shows a common binary tree:

The characteristics of binary tree

From the definition of binary tree and graphic analysis, it is concluded that binary tree has the following characteristics:

1) each node has at most two subtrees, so there are no nodes with degree greater than 2 in the binary tree.

2) the left subtree and the right subtree are in order, and the order cannot be reversed arbitrarily.

3) even if there is only one subtree at a node in the tree, it is necessary to distinguish whether it is a left subtree or a right subtree.

The properties of binary tree

1) there are at most 2i-1 nodes on the I layer of the binary tree. (I > = 1)

2) if the depth in the binary tree is k, then there are at most 2k-1 nodes. (K > = 1)

3) n0=n2+1 N0 represents the number of nodes with degree 0, and N2 represents the number of nodes with degree 2.

4) in a complete binary tree, the depth of a complete binary tree with n nodes is [log2n] + 1, where [log2n] is rounded down.

Binary tree traversal

The so-called traversal means that each node in the tree is visited once and only once along a certain search route. The operation done by the access node depends on the specific application question. Traversal is one of the most important operations on binary tree, and it is the basis of other operations on binary tree.

The traversal of binary tree can be divided into depth first and breadth first, in which depth priority includes pre-order traversal, middle-order traversal and post-order traversal, which is determined by the traversal order of root nodes and left and right subtrees.

The preorder traversal is to visit the root node and then to the left subtree and then to the right subtree; the middle order traversal is to visit the left subtree and then to the root node and finally to the right subtree; the post-order traversal is to visit the left subtree and then the right subtree and finally to the root node.

Breadth-first traversal is accessed by layer from top to bottom from the root node, and each layer is accessed from left to right.

These traversal methods and their code implementation are described below.

Binary tree node definition

The binary tree node defined by python code is as follows:

Figure a (binary tree)

Preorder traversal

The idea of recursion is easy to understand, starting from the root node of the binary tree, when it reaches the node for the first time, it outputs the node data and accesses it in the direction of first to left and to right. The preorder traversal output of the binary tree is: ABDHIEJCFG

The python code is implemented as follows:

The idea of non-recursive traversal is as follows:

1) define a stack

2) push the root node into the stack

3) every time the node pops up from the stack as cur and prints. If the right child is not empty, press the right child into the stack. If the left child is not empty, press the left child into the stack.

4) repeat step 3 until the stack is empty

The python code is implemented as follows:

Mid-order traversal

The recursive idea realizes the traversal order in the middle order, first traversing the left subtree, then visiting the root node, and finally traversing the right subtree. The middle order traversal output of the binary tree is: HDIBJEAFCG

The python code is implemented as follows:

The idea of non-recursive traversal is as follows:

1) apply for a stack stack, and apply for a variable cur to point to the header node

2) press the head node into the stack first, and for the whole subtree with cur as the head node, press the left boundary of the whole tree into the stack in turn, that is, keep making cur=cur.left

3) repeat step 2 until cur is empty, then pop the node node from the stack and print it, then cur=node.right, and then repeat step 2

4) ends when stack is empty and cur is empty.

The python code is implemented as follows:

Post-order traversal

The recursive idea implements the post-order traversal order, first traversing the left subtree, then traversing the right subtree, and finally visiting the root node. The post-order traversal output of the binary tree is: HIDJEBFGCA

The python code is implemented as follows:

The idea of non-recursive traversal is as follows:

1) apply for two stacks S1, and then press the head node into S1

2) the node that pops up from S1 is marked as cur and added to stack S2, then the left child of cur is pressed into S1, and then the right child of cur is pressed into S1.

3) repeat 2 until S1 is empty

4) eject the node from S2 and print

The python code is implemented as follows:

Breadth first (sequence) traversal

Breadth first (sequence traversal) is realized by queues, traversing layer by layer from top to bottom, starting from the first layer of the binary tree (root node). In the same layer, the nodes are accessed one by one in the order from left to right.

Access the nodes of the binary tree in the order from the root node to the leaf node and from the left subtree to the right subtree.

Algorithm:

1. Initialize a queue and queue the root node

2. When the queue is listed as non-empty, cycle through steps 3 to 5, otherwise execute 6

3. Get a node out of the queue and visit the node

4. If the left subtree of the node is non-empty, the left subtree of the node is queued

5. If the right subtree of the node is non-empty, the right subtree of the node is queued

6. End.

The python code is implemented as follows:

On how to analyze the python binary tree to share here, I hope that the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.