[data structure] binary tree

Directory

1. Tree structure

1. Concept (Understanding)

2. Concept (important)

3. Tree representation

4. Application of trees

2. Binary tree (emphasis)

1. Concept

2. Two special binary trees

4. Binary tree storage

5. Basic operation of binary tree

5.1 Prerequisites

5.2 Binary tree traversal

1. Tree structure

1. Concept (Understanding)

A tree is a non-linear data structure, which is a set of hierarchical relationships composed of n (n>=0) finite nodes. It is called a tree because it looks like an upside-down tree, which means it has the roots pointing up and the leaves pointing down. It has the following characteristics:
There is a special node called the root node, the root node has no predecessor node
Except the root node, the other nodes are divided into M (M > 0) mutually disjoint sets T1, T2, …, Tm, each set Ti (1 <= i <= m) and is a subtree similar to a tree. The root node of each subtree has one and only one predecessor, can have 0 or more successors

Trees are defined recursively.

In the tree structure, there can be no intersection between subtrees, otherwise it is not a tree structure

2. Concept (important)

The degree of a node: The number of subtrees contained in a node is called the degree of the node; as shown in the figure above: the degree of A is 6

Tree degree: In a tree, the maximum value of all node degrees is called the tree degree; as shown in the figure above: The degree of the tree is 6 (hex tree)

Leaf node or terminal node: A node with degree 0 is called a leaf node; as shown in the figure above: B, C, H, I… and other nodes are leaf node

Parent node or parent node: If a node contains child nodes, this node is called the parent node of its child nodes; as shown above: A is the parent node of B

Child node or child node: the root node of the subtree contained in a node is called the child node of the node; as shown above: B is the child node of A

Root node: In a tree, there is no parent node node; as shown above: A

Node level: starting from the definition of the root, the root is the first level, the child nodes of the root are the second level, and so on

Tree height or depth: Maximum level of nodes in the tree; as shown above: the height of the tree is 4

You only need to understand the following concepts of the tree, and you only need to know what it means when reading a book:

Non-terminal node or branch node: a node whose degree is not 0; as shown in the figure above: nodes such as D, E, F, G… are branch nodes

Sibling nodes: Nodes with the same parent node are called sibling nodes; as shown above: B and C are sibling nodes

Cousin nodes: Nodes whose parents are on the same layer are cousins; as shown in the figure above: H and I are sibling nodes

Ancestor of a node: all nodes on the branch from the root to the node; as shown in the figure above: A is the ancestor of all nodes

Descendants: Any node in the subtree rooted at a node is called a descendant of the node. As shown above: all nodes are descendants of A

Forest: A collection of m (m>=0) disjoint trees is called a forest

3. Tree representation

The tree structure is more complicated than the linear table, and it is more troublesome to store and express. In practice, there are many ways to express the tree, such as: Parent representation,

Child Notation, Child Parent Notation, Child Sibling Notation, etc. Here we simply understand the most commonly used child brother notation.

class Node {
int value; // data stored in the tree
Node firstChild; // first child reference
Node nextBrother; // next brother reference
}

4. Applications of trees

File system management (directories and files)

Seeing the tree structure is a natural search semantics (compared to a linear structure, finding elements is much faster!)

Second, binary tree (key point)

1. Concept

A binary tree is a finite set of nodes that:

or empty

Or it is composed of a root node plus two binary trees called left subtree and right subtree.

As can be seen from the figure above:

There is no node with degree greater than 2 in the binary tree

The subtrees of a binary tree are divided into left and right, and the order cannot be reversed, soA binary tree is an ordered tree
[Note] For any binary tree, it is composed of the following situations:

2. Two special binary trees

1. Full binary tree: A binary tree, if the number of nodes in each layer reaches the maximum value, then this binary tree is a full binary tree. That is to say, if the number of layers of a binary tree is K, and the total number of nodes is , the number of nodes in the kth layer is 2*(k – 1), then it It is a full binary tree.
2. Complete binary tree: A complete binary tree is a very efficient data structure, and a complete binary tree is derived from a full binary tree. For a binary tree with a depth of K and n nodes, if and only if each node corresponds to a node numbered from 0 to n-1 in a full binary tree with a depth of K strong> is called a complete binary tree. It should be noted that full binary tree is a special kind of complete binary tree. (full binary tree only lacks the lower right corner, and the left side is all there)(there is at most one node with degree 1)(seeing that the number of nodes in a complete binary tree is odd, it is impossible to have a node with degree 1 )

3. Properties of binary trees

1. If the number of layers of the root node is specified as 1, then there are at most (i>0) nodes
2. If the depth of a binary tree with only root nodes is specified as 1, then the maximum number of nodes in a binary tree with a depth of K is (k>=0)
3. For any binary tree, if the number of leaf nodes is n0 and the number of non-leaf nodes with degree 2 is n2, then there is n0=n2+1( There is one more node with degree zero than node with degree 2)
4. The depth k of a complete binary tree with n nodes is round up
5. For a complete binary tree with n nodes, if all nodes are numbered from 0 in order from top to bottom and from left to right, then for the node with sequence number i have:
   If i>0, parent number: (i-1)/2; i=0, i is the root node number, no parent node
   If 2i + 1 If 2i + 2
6. Complete binary tree: the root node of the tree is numbered from 1, if the number of a node is k, the left subtree is 2k, and the right subtree is 2k + 1; regress the parent Node k/2. The root node of the tree is numbered from 0. If the number of a node is k, the left subtree is 2k + 1, and the right subtree is 2k + 2; reverse the parent node (k – 1)/2.

【Exercise】

There are 399 nodes in a binary tree, among which there are 199 nodes with degree 2, then the number of leaf nodes in the binary tree is ( )
A There is no such binary tree
B 200
C 198
D 199
2. In a complete binary tree with 2n nodes, the number of leaf nodes is ( )
An
B n + 1
C n-1
D n/2
3. A complete binary tree with 767 nodes, the number of leaf nodes is ()
A 383
B 384
C 385
D 386
4. The number of nodes in a complete binary tree is 531, then the height of this tree is ( )
A 11
B 10
C 8
D 12

【Answer】
1.B Binary tree has one more node with degree zero than node with degree 2
2. A The number of leaf nodes is n0, the number of non-leaf nodes with degree 2 is n2, and the number of non-leaf nodes with degree 1 is n1=1 (A complete binary tree has at most one degree 1 node)

3.B (Seeing that the number of nodes in a complete binary tree is odd, it is impossible to have a node with a degree of 1) -> n1=0, n0=n2 + 1, n0 + n2=767, the answer to the equation will come out up
4.B Look at the fourth point of the nature of the binary tree

4. Binary tree storage

The storage structure of binary tree is divided into: sequential storage and linked storage similar to linked list.
The chained storage of the binary tree is referenced by nodes one by one. The common representations are binary and ternary representations, as follows:

class Node {
    int val; // data field
    Node left; // A reference to the left child, often representing the entire left subtree rooted at the left child
    Node right; // A reference to the right child, often representing the entire right subtree rooted at the right child
}
// child parent representation
class Node {
    int val; // data field
    Node left; // A reference to the left child, often representing the entire left subtree rooted at the left child
    Node right; // A reference to the right child, often representing the entire right subtree rooted at the right child
    Node parent; // the root node of the current node
}

The postorder of the child parent representation is introduced at the position of the balanced tree. This paper uses the child representation to construct a binary tree.

5. Basic operation of binary tree

5.1 Prefix

Before learning the basic operations of a binary tree, you need to create a binary tree before you can learn its related basic operations. Since the grasp of the binary tree structure is not deep enough, in order to reduce the learning cost, here is a quick manual to create a simple binary tree, and quickly enter the binary tree operation learning. When the binary tree structure is almost understood, we will turn around and study the real creation method of the binary tree .

public class MyBinTree {
    private class TreeNode {
        char val;
        TreeNode left;// The reference of the left child, often representing the entire left subtree rooted at the left child
        TreeNode right;// The reference of the right child, often representing the entire right subtree rooted at the right child
        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode build() {
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');
        TreeNode node7 = new TreeNode('G');
        TreeNode node8 = new TreeNode('H');
        node1. left = node2;
        node1.right = node3;
        node2. left = node4;
        node2.right = node5;
        node5.right = node8;
        node3. left = node6;
        node3.right = node7;
        return node1;
    }
}

[Note] The above code is not a way to create a binary tree. The actual way to create a binary tree will be explained in detail later.
Before looking at the basic operations of the binary tree, review the concept of the binary tree. The binary tree is:

(1) empty tree

(2) Non-empty: the root node, the left subtree of the root node, and the right subtree of the root node. It can be seen from the concept that the definition of a binary tree is recursive, so the basic operations of the subsequent order are basically implemented according to this concept.

5.2 Binary tree traversal

(1) Front, middle and back order traversal
The easiest way to learn the binary tree structure is to traverse it. The so-called traversal (Traversal) refers to following a certain search route, making one and only one visit to each node in the tree in turn. The operation of accessing the node depends on the specific application problem (for example: print the node content, add 1 to the node content). Traversal is one of the most important operations on the binary tree, and it is the basis for other operations on the binary tree.

Breadth-first traversal BFS: Breadth-first needs to traverse all possible positions in the next step before performing deeper traversal. Layer-order traversal is a kind of breadth-first traversal.

Depth-first DFS: Depth-first is to traverse a complete path (from the root to the leaf) before turning back to the upper layer and then traversing the next path. Preorder traversal is a kind of Depth-first traversal.

When traversing a binary tree, if there is no agreement and everyone traverses in their own way, the result will be confusing. If an agreement is made according to a certain rule, everyone’s traversal results for the same tree must be the same of. If N represents the root node, L represents the left subtree of the root node, and R represents the right subtree of the root node, then according to the order of traversing the root nodes, there are the following traversal methods:
NLR:Preorder Traversal (also known as preorder traversal) (depth-first DFS) – visit the root node —> the left subtree of the root —> the right subtree of the root. (The first result of the pre-order traversal must be the root node of the current tree ~ [recursive satisfaction]) (the first time to go)
LNR: Inorder Traversal(Inorder Traversal)–the left subtree of the root—>root node—>the right subtree of the root. (In the result set of in-order traversal, the results of the left subtree must be on the left side of the current root node, and all the results of the right subtree must be on the right side of the current root node ~ [recursive satisfaction]) (the second time)< /strong>
LRN: Postorder Traversal–the left subtree of the root —> the right subtree of the root —> the root node. (The reverse result of the post-order traversal is the mirror image result of the pre-order traversal (root right left)) (the third time to go)
The following mainly analyzes the pre-order recursive traversal, and the in-order and post-order diagrams are similar.

// Preorder traversal
void preOrder(Node root);
// inorder traversal
void inOrder(Node root);
// Post-order traversal
void postOrder(Node root);