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

How to analyze python binary tree and multi-tree, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

1. Tree structure 1, array and linked list

Array structure

Array storage accesses elements through subscript, and the query speed is fast. If the array elements are ordered, binary search can be used to improve the retrieval speed. If you add new elements, it may cause multiple subscript movement, which is inefficient.

Linked list structure

Linked list stores elements, which is efficient for adding and deleting elements, but traversing elements needs to start from the header node every time, so the efficiency is very low.

Tree structure can improve the efficiency of data storage and reading at the same time.

2. The concept of tree structure

Root node: the root of the tree, a node without a parent, as shown in figure An above

Sibling node: a child node that has the same parent node. As shown in figure B and C

Leaf node: a node that has no child nodes. DEFG node as shown in the figure

Height of the tree: the maximum number of layers, as shown in the figure of 3

Path: find the route of the specified node from the root root node

The tree structure is a hierarchical nested structure. The outer and inner layers of a tree structure have a similar structure, so this structure can be represented recursively. All kinds of trees in classical data structures are typical tree structures: a tree can be simply represented as root, left subtree and right subtree. The left subtree and the right subtree have their own subtrees.

Binary tree model

There are many kinds of trees. BinaryTree is an important type of tree structure. Each node can only have at most two child nodes, which is called binary tree. The child nodes of binary tree are divided into left node and right node. The data structure abstracted from many practical problems is often in the form of binary tree.

Complete binary tree

All the leaf nodes of the binary tree are in the last layer or the penultimate layer, and the leaf nodes of the last layer are continuous on the left, and the leaf nodes of the penultimate layer are continuous on the right. We call them complete binary trees.

Full binary tree

When all the leaf nodes of a binary tree are at the last layer, and the total number of nodes = 2 ^ n-1, n is the number of layers, it is called a full binary tree.

Balanced binary tree

The balanced binary tree means that the absolute value of the height difference of the subtree of any node is less than or equal to 1, and the left and right subtrees are a balanced binary tree. The common balanced trees are B-tree (multipath balanced search tree), AVL tree (binary balanced search tree) and so on.

Binary search tree

Binary search tree (BinarySearchTree) is not only a binary tree, but also satisfies a certain order: the left child node of the node is smaller than itself, and the right child node of the node is larger than itself.

3. Binary tree coding 1. Basic code

Node code

Class TreeNode {private String num; private TreeNode leftNode; private TreeNode rightNode; public TreeNode (String num) {this.num = num;} @ Override public String toString () {return "TreeNode {num=" + num +'}';}}

Tree structure code

Class BinaryTree01 {private TreeNode root;} 2, traversal and lookup

Preorder traversal lookup

First process the data of the current node, and then recursively traverse the left subtree and the right subtree

Public void prevTraverse () {/ / output parent node System.out.println (this); / / Recursive preorder traversal if (this.leftNode! = null) {this.leftNode.prevTraverse ();} / Recursive preorder traversal if (this.rightNode! = null) {this.rightNode.prevTraverse () to the right subtree } public TreeNode prevSearch (String num) {/ / compare the current node if (this.num.equals (num)) {return this;} / Recursively traverse the left subtree to find TreeNode findNode = null; if (this.leftNode! = null) {findNode = this.leftNode.prevSearch (num);} / / the left subtree traversal hits if (findNode! = null) {return findNode } / / Recursively traverse the right subtree to find if (this.rightNode! = null) {findNode = this.rightNode.prevSearch (num);} return findNode;}

Mid-order traversal search

First recursively traverse the left subtree, then deal with the parent node, and then recursively traverse the right subtree

Public void midTraverse () {/ / recursively traverses if (this.leftNode! = null) {this.leftNode.midTraverse ();} / outputs parent node System.out.println (this) to the left subtree; / / recursively traverses if (this.rightNode! = null) {this.rightNode.midTraverse () to the right subtree. } public TreeNode midSearch (String num) {/ / Recursively traverse the left subtree to find TreeNode findNode = null; if (this.leftNode! = null) {findNode = this.leftNode.midSearch (num);} if (findNode! = null) {return findNode;} / compare the current node if (this.num.equals (num)) {return this } / / Recursively traverse the right subtree to find if (this.rightNode! = null) {findNode = this.rightNode.midSearch (num);} return findNode;}

Post-order traversal lookup

First recursively traverse the left subtree, then recursively traverse the right subtree, and finally deal with the parent node

Public void lastTraverse () {/ / recursively traverses if (this.leftNode! = null) {this.leftNode.lastTraverse ();} / recursively traverses if (this.rightNode! = null) {this.rightNode.lastTraverse ();} / outputs parent node System.out.println (this) to the right subtree. } public TreeNode lastSearch (String num) {/ / Recursively traverse the left subtree to find TreeNode findNode = null; if (this.leftNode! = null) {findNode = this.leftNode.lastSearch (num);} if (findNode! = null) {return findNode;} / Recursively traverse the right subtree to find if (this.rightNode! = null) {findNode = this.rightNode.lastSearch (num) } if (findNode! = null) {return findNode;} / / compare the current node if (this.num.equals (num)) {return this;} return null;} 3. Delete node

If the currently deleted node is a leaf node, you can delete it directly; if the deleted node is a non-leaf node, delete the node tree.

Public void deleteNode (String num) {/ / determine whether the left node deletes if (this.leftNode! = null & & this.leftNode.num.equals (num)) {this.leftNode = null; return;} / / determine whether the right node deletes if (this.rightNode! = null & & this.rightNode.num.equals (num)) {this.rightNode = null; return } / / Recursive deletion of if (this.leftNode! = null) {this.leftNode.deleteNode (num) to the left subtree traversal;} / / Recursive deletion of if (this.rightNode! = null) {this.rightNode.deleteNode (num) to the right subtree;}} Quad, multitree

Multi-tree means that a parent node can have multiple child nodes, but a child node still follows the law of a parent node. In general, the practical application height of binary tree is too high, so the description of data relationship can be simplified by multi-tree. For example, Linux file system, organizational structure relationship, role menu rights management system, etc., are usually described based on multi-tree.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, 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.