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

Today, I will talk to you about how to create a python binary tree according to preorder traversal and mid-order traversal. Many people may not know much about it. 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.

Contents

Introduction to the introduction of four methods for traversing trees two methods for quickly obtaining traversal results create tree codes to realize four methods of traversing trees according to preorder traversal and subsequent traversal

To cut the crap, here's how to create a binary tree based on pre_order and in_order.

A brief introduction to four methods of traversing trees

First of all, here is a brief introduction to the four traversal ways of binary tree:

Preorder traversal (pre_order)

Mid-order traversal (in_order)

Post-order traversal (post_order)

Sequence traversal (level_order)

The traversal code is placed at the end of the article.

Preorder traversal is to operate on the current root node, then to the left child node, and then to the right child node!

Traversal in the middle order is to operate on the current left child node, then to the current root node, and then to the right child node!

Post-order traversal is to operate on the current left child node, then to the right child node, and then to the current root node!

Sequence traversal is to operate on each node from top to bottom, from left to right! The code is a little more complicated than the first three, with the help of queues and iteratively.

The following picture (notes taken before class):

Two methods for quickly obtaining traversal results

In addition, two traversal results of pre-order, post-order and middle order can be quickly obtained according to the shape of the tree.

Law one:

Law II:

Create a tree based on preorder traversal and subsequent traversal

Give you an array, use the values of this array to create a tree, the result has a variety of possibilities:

Where n is the number of elements in the array!

However, if we give two arrays, the result of preorder traversal and subsequent traversal, then we can create a unique tree!

Note: requires that the elements in the array are not duplicated and are unique!

After looking at the traversing methods facing the tree, you can find:

Note: the following process is a little boring, and I don't describe it very well. You can look at the figure below.

The first element of the preorder traversal is the root node of the tree; the second element is the left child node of the root node, which is also the subsequent root node.

The root node divides the middle order traversal array into two. In the middle order traversal array: the left side of the root node is the left tree, and the right side of the root node is the right tree.

Therefore, we traverse the array traversed in the preorder, and the current index is pre_i. In each traversal, we find the corresponding value of the pre_i in the array traversed in the middle order, and use this pre_i to divide the result of the traversal in the middle order into two. If you go back and forth, you can restore the tree.

Let me draw the whole process:

That's about it, constantly dividing the array traversed in the middle order into two (split according to the current element of the array traversed in the previous order); the current element of the array traversed in the middle order is the current root node.

Code implementation

Define the nodes of the tree first:

Template

Struct Node {

T val

Node* left

Node* right

Explicit Node (T v): val (v), left (nullptr), right (nullptr) {}

}

Create a tree based on preorder traversal and mid-order traversal:

/ * *

* @ brief creates a tree based on preorder traversal and intermediate order traversal

* @ param [in] pre_vec preorder traversal array

* @ param [in] in_vec ordered traversal array

* @ param [in] left_in traverses the left boundary of the current segment in order

* @ param [in] right_in traverses the right boundary of the current segment in order (overtailed)

The current index of * @ static pre_i preorder traversal

*

* @ note in each layer of recursion, the current traversal array segment is divided into: [left_in, pre_i), pre_i, [pre_i+1, right_in)

* * /

Template

Node* CreateTreeR (vector& pre_vec, vector& in_vec, int left_in, int right_in)

{

Static int pre_i = 0

If (left_in

< right_in) { /// 从 前序遍历 的数组中 获取 当前 根节点！ T cur_root_val = pre_vec.at(pre_i); auto* cur_root = new Node(cur_root_val); /// 遍历 中序遍历 的数组，找到当前根节点对应的索引 int i = left_in; while (i < right_in && cur_root_val != in_vec.at(i)) ++i; /// 下次递归前 pre_i 是需要向后移动一位的 ++pre_i; /// 一分为二！(注意，i是当前节点的索引哦！) cur_root->

Left = CreateTreeR (pre_vec, in_vec, left_in, I); / left tree

Cur_root- > right = CreateTreeR (pre_vec, in_vec, iTun1, right_in); / right tree

Return cur_root

}

/ / when there is only one element left, empty is returned.

Return nullptr

}

Test this program

For the created tree, use four traversal methods to traverse at once, four kinds of traversal code at the end of the article.

The one above is numeric. I'll try it with a string now:

Code for four methods of traversing the tree

1. Sequence traversal:

/ * *

Sequence traversal of * @ brief trees

* * /

Template

Void LevelOrder (Node* root, vector& vec)

{

/ / return directly if the root node is empty

If (! root) return

/ define a queue to place all the nodes that may become "root nodes" (a "root node" will be pop out of each loop)

Queue

< Node* >

Q

Q.push (root)

While (! q.empty ()

{

/ / take the front root node out of the queue

Node* cur_root = q.front (); / this variable is better declared outside while instead of creating a new variable every time.

Q.pop ()

/ / Save the value of the current "root node"

Vec.push_back (cur_root- > val)

/ / if the left child node is not empty, put the left child node in the queue

If (cur_root- > left)

Q.push (cur_root- > left)

/ / put the right child node in the queue if the right child node is not empty

If (cur_root- > right)

Q.push (cur_root- > right)

}

}

two。 Preorder traversal:

/ * *

Preorder traversal of * @ brief tree

* * /

Template

Void PreOrder (Node* root, vector& vec)

{

If (root)

{

Vec.push_back (root- > val)

PreOrder (root- > left, vec)

PreOrder (root- > right, vec)

}

}

3. Traversal in the middle order:

/ * *

Mid-order traversal of * @ brief trees

* * /

Template

Void InOrder (Node* root, vector& vec)

{

If (root)

{

InOrder (root- > left, vec)

Vec.push_back (root- > val)

InOrder (root- > right, vec)

}

}

4. Traversal in the following order:

/ * *

Post-order traversal of * @ brief trees

* * /

Template

Void PostOrder (Node* root, vector& vec)

{

If (root)

{

PostOrder (root- > left, vec)

PostOrder (root- > right, vec)

Vec.push_back (root- > val)

}

}

After reading the above, do you have any further understanding of how to create a python binary tree based on preorder traversal and intermediate order traversal? 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.