Definition of 1. tree

Tree is a common nonlinear data structure. The recursion of a tree is defined as follows:

This tree is n (n > 0) A finite node set that meets the following conditions:

(1) There is only one node without antecedent (parent node), and this node is called the root of the tree;

(2) Except the root, every other node has one and only one antecedent;

(3) Except the root, each node is connected to the root through a unique path. This path starts from the root and ends at this node, and every node on the path is the successor (child node) of the previous node except the root;

2. Node classification

In a tree, a node contains an element and all branches pointing to its subtree. Nodes are generally divided into three categories.

⑴ Root node: a node without antecedents. There is only one root node in the tree.

⑵ Branch node: Except the root node, the node with the postposition is called a branch node. The branch node is also the root of its subtree;

(3) Leaf nodes: nodes without tails are called leaves. According to the definition of a tree, a leaf itself is also a subtree of its parent node.

The path from the root node to each branch node or leaf node is unique.

3. Definition of correlation degree

⑴ Degree of a node: The number of subtrees of a node is called the degree of the node. show

However, the degree of all leaves is 0.

⑵ Degree of the tree: The largest degree among all nodes is called the degree of the tree. 4, the depth of the tree (height)

Trees are hierarchical. The level of a node is calculated from the root. The root node is at the first level, the back part of the root is at the second level, and so on. That is, if a node is at the k-th layer, the subsequent part of the node is at the k+ 1 layer. The tree in figure (b) has five layers. In the tree, all nodes whose parent nodes are at the same level form a sibling relationship. The largest level in the tree is called the depth of the tree, also called the height.

5. Ordered trees and unordered trees

According to whether the nodes at the same level in the tree remain orderly, the tree can be divided into ordered trees and disordered trees. If the nodes at the same level in the tree are arranged from left to right, the order cannot be interchanged. Such a tree is called an ordered tree. If the order of nodes at the same level is arbitrary, such a tree is called unordered tree.

6. Tree representation

There are usually two ways to represent a tree:

(1) Natural tree representation: A tree is represented by nodes and edges. For example, the above picture adopts the tree representation of nature. Tree representation is generally used to analyze problems.

⑵ Bracket representation: first put the root node in a pair of brackets, then put its subtree in brackets from left to right, and the subtree is treated in the same way: the subtree at the same level is enclosed in brackets with its root node, separated by commas, and finally enclosed by closed brackets. For example, a chart can be written in the following form

(r(a(w，x(d(h)，e))，b(f)，c(s，t(i(m，o，n)，j)，u)))

7. Trees usually have two storage structures.

(1) static record array. All nodes are stored in an array, and the elements of the array are of record type, including data fields and an array of length n(n is the degree of the tree), and the subscripts of each node are stored separately.

⑵ Dynamic multiple linked list. Because nodes in a tree can have multiple elements, it is convenient to describe them with multiple linked lists. The so-called multiple linked list means that each node consists of a data field and n pointer fields ***n+ 1 fields.

The following is about binary trees:

The concept of binary tree

Binary tree is a very important nonlinear data structure. Its characteristic is that each node has at most two successors, and its subtree is divided into left and right (the order cannot be reversed arbitrarily).

1, recursive definition and basic form of binary tree

A binary tree is a finite set with nodes as elements, which is either empty or meets the following conditions:

(1) has a specific node called root;

⑵ Divide the remaining nodes into disjoint subsets L and R, where R is the left subtree of the root; L is the right subtree of the root; L and r are binary trees;

As can be seen from the above definition, binary tree and tree are two different concepts.

Each node of the (1) tree can have any number of postpositions, and each node in the binary tree cannot have more than two postpositions;

(2) The subtrees of a tree can be unordered (except ordered trees); The subtree of a binary tree has left and right points. We call the left rear part of a node in a binary tree a left sub and the right rear part a right sub.

2. Two special forms of binary tree

⑴ Full binary tree: If any node of a binary tree is a leaf, or there are exactly two non-empty trees, the binary tree is called full binary tree. It can be verified that a full binary tree with n leaf nodes * * * has 2n- 1 nodes.

⑵ Complete binary tree: A binary tree is called a complete binary tree if at most only the nodes in the bottom two layers can be less than 2, and all the nodes at the bottom are concentrated in the leftmost position of the layer.

3. Three main properties of binary tree

Property 1: On the i(≥ 1) layer of a binary tree, there are at most 2i- 1 nodes.

Proof: We prove that there is only one root node when i= 1, that is, 2i- 1=20= 1, and the conclusion is valid. Assume that the k(i=k) layer has at most 2k- 1 nodes, and consider i=k+ 1. By induction, it is assumed that there are at most 2k- 1 nodes on the k layer of a binary tree, and each node has at most two child nodes, then there are at most 2.2k-1= 2 (k+ 1)-1= 2i on the k+/kloc/layer, and the conclusion is valid. To sum up, real estate 1 is established.

Property 2: A binary tree with a depth of k(k≥ 1) has at most 2k- 1 nodes.

From the property of 1, it is proved that the I layer of binary tree has at most 2i- 1 nodes. Obviously, the maximum number of nodes on the 1 layer (k layer) is nodes. Complete the certificate.

Property 3: In any binary tree, the number of leaf nodes is always more than that of nodes with degree 2 1.

Prove: Let n0 be the number of leaf nodes of binary tree; N 1 is the number of nodes with degree 1 in the binary tree; N2 is the number of nodes with degree 2 in the binary tree, and obviously n=n0+n 1+n2 (1).

Because each node in a binary tree has only one antecedent except the root node. Let b be the number of antecedents of a binary tree, and n=b+ 1(2).

All these antecedents are also the rear parts of nodes with degrees 1 and 2. So there is b=n 1+2n2 (3).

We substitute (3) into (2) and get n=n 1+2n2+ 1 (4).

Comparing (1) and (4), it is concluded that n0=n2+ 1, that is, the number of leaves is more than the number of nodes with degree 2 1.

4. Convert ordinary ordered trees into binary trees.

Ordinary trees are ordered trees T, and the rules for transforming them into binary trees T' are as follows:

The nodes in (1)T correspond to the nodes in T', that is, the serial number and value of each node in T remain unchanged in T';

⑵ The first child of a node V in T is v 1, so v 1 in T' is the left child of the corresponding node V;

(3) the subsequence of node V in T is linked into the right chain from v 1 in T' in turn;

As can be seen from the above transformation rules, the root node of an ordered tree transformed into a binary tree has no right subtree, and all branches except the leftmost branch of each node should be removed, and then all the children of the node should be linked in turn in the right sub-direction from the leftmost child.

5. Storage structure of binary tree

Each node is stored in a one-dimensional array in turn, and the node number is represented by an array subscript. The numbering method is to number 1 from the root node and then number continuously from left to right. The information of each node includes

(1) data field (data);

⑵ Three pointer fields, including parent node number (prt), left child node number (lch) and right child node number (rch).

Full binary tree and full binary tree generally adopt sequential storage structure.

For general binary trees, chain allocation is usually adopted, that is, a bidirectional linked list is used to represent general binary trees. This chain allocation can adopt static data structure (array) or dynamic data structure (pointer). If the storage requirement of binary tree exceeds 64Kb, the latter is adopted. Because each node in a binary tree usually includes a data element and two branches. Therefore, each node in the bidirectional linked list corresponding to a binary tree should have three domains:

(1) range: data

⑵ Left pointer field: lch

⑶ Right pointer field: rch

This linked list is also called binary linked list. The head pointer bt of the binary linked list points to the root node of the binary tree.

6. Traversal of Binary Tree

The definition of binary tree traversal: according to certain rules, every node in the binary tree is not visited repeatedly (or the information in the node is taken out, or the node is processed in other ways).

The order of binary tree traversal: If L, D and R are used to represent traversal of left subtree, access to root node and traversal of right subtree respectively, there are six kinds of binary tree traversal (3! =6) Combination: LDR, LRD, DLR, DRL, RDL, RLD. If the order is defined from left to right, there are only three combinations: LDR (middle order traversal), LRD (post order traversal) and DLR (pre-order traversal).

The rules of preorder traversal are as follows:

If the binary tree is empty, exit. otherwise

(1) Access the root node;

(2) The preorder traverses the left subtree;

(3) The preorder traverses the right subtree;

Features: visit the branches of the tree one by one from left to right from the root (the basis of backtracking method)

Rules for intermediate sequence traversal:

If the binary tree is empty, exit; otherwise

(1) The intermediate sequence traverses the left subtree;

(2) accessing and processing the root node;

(3) Traverse the right subtree in the middle order;

The rules for postorder traversal are as follows:

If the binary tree is empty, exit; otherwise

(1) traverses the left subtree in turn;

(2) Traverse the subtree on the right in turn;

(3) access the root node;

Features: You can count subtrees with any node as the root (for example, the weighted sum of subtrees, the choice of optimal strategy (the number of games)).