Introduction to python data structure trees and binary trees

  • 2020-04-02 13:39:31
  • OfStack

The definition of a tree

Tree structure is an important nonlinear structure. A tree structure is a structure with branches and hierarchical relationships between nodes. It is very similar to trees in nature.
Recursive definition of tree:
Tree is the finite set T of n(n p 0) nodes. When T is empty, it is called an empty Tree. Otherwise, it satisfies the following two conditions:
(1) there is and only one specific node called Root;
(2) the remaining nodes can be divided into m(m p 0) mutually disjunction subsets Tl, T2... Tm, where each subset itself is a tree and is called a subtree of the root.

Two, the definition of binary tree

Binary tree is an ordered tree with a finite set of n (n p 0) nodes and at most two subtrees per node. It is either an empty set, or it consists of a root and two disjoint binary trees called left and right subtrees.
Features:
(1) binary trees are ordered trees. Even if there is only one subtree, the left and right subtrees must be distinguished.
(2) the degree of each node of the binary tree cannot be greater than 2, and it can only be one of 0, 1 and 2.
(3) there are five forms of all nodes in binary trees: nil, nodes without left and right subtrees, nodes with only left subtree, nodes with only right subtree and nodes with left and right subtrees.

Properties of binary trees

Property 1: there is no more than one node on the I layer of binary tree.
Property 2: a binary tree with depth h has at most -1 node.
Property 3: the largest integer whose height is not less than the binary tree with n nodes.
Property 4: in any binary tree, if the number of leaf nodes is n0 and the number of nodes with degree 2 is n2, there must be n0 = n2+1.
Full binary tree: if the depth of h of the binary tree, it happens to have -1 node, is called a full binary tree.
Complete binary tree: if the logical structure of a binary tree with n nodes is exactly the same as that of the first n nodes of a full binary tree, the binary tree is called a complete binary tree
Extended binary tree: every node except the leaf must have a binary tree with two children.

Storage structure of binary tree

The binary tree storage structure has the sequential storage structure, the chain storage structure
Sequential storage: The structure is stored as a one-dimensional array. According to the property of binomial tree 6, the subscripts of parent node and left and right child node can be calculated. Therefore, the storage of full binary tree and complete binary tree can adopt one-dimensional array, and the nodes are stored in the array from top to bottom and from left to right. The relationship between nodes can be calculated by the formula of property 6.
Chain storage: The structure USES the linked list to store the data elements in the binary tree. The most commonly used chain storage structure of binary tree is binary chain, each node contains three domains, namely data of data element domain, lChild of left child chain domain and rChild of right child chain domain. The binary tree of binary chain storage structure also has two kinds of lead node and non-lead node, which are similar to the cases of lead node and non-lead node in single linked list

Five, binary tree operation

(link: #)
(link: #)
(link: #)


Related articles: