Collection of Binary Trees (1): Basics of Binary Trees (including four kinds of traversal, detailed explanation of pictures and texts)

Collection of Binary Trees (1): Basics of Binary Trees (including four kinds of traversal, detailed explanation of pictures and texts)

Collection address

Binary Tree Collection (1): Binary Tree Basics (including four types of traversal, detailed with graphic and text)
Binary Tree Collection (2): Hoffman Tree (detailed with graphic and text)
Binary Tree Collection (3): clue Binary Tree (detailed with graphic and text)
Binary Tree Collection (4) ): Symmetric binary tree (recursive and iterative implementation)
Binary tree collection (5): Binary search tree (detailed picture, including basic operations)
Binary tree collection (6): Highly balanced binary tree

Preface

Trees are the most important part of the data structure, especially the difficulty of learning all kinds of binary trees. For a long time, the mastery of trees has been ambiguous, and now I hope to write a series on binary trees. While learning and summarizing, we have a deeper understanding and mastering of binary trees. This series of articles will focus on general binary trees, complete binary trees, full binary trees, clue binary trees , Huffman trees , binary sort trees , balanced binary trees, red-black trees, and B-trees. I hope that readers can pay attention to the topic and give corresponding opinions, so as to have a "tree" in mind through a series of learning.

1 Key concepts

1.1 Node concept

The node is the foundation of the data structure and the basic unit of the complex data structure.

1.2 Tree node declaration

The nodes mentioned in this series of articles refer specifically to the nodes of the tree. For example: Node A is represented in the figure as:

tree

2.1 Definition

**Tree** is a finite set of n (n>=0) nodes. When n=0, it is called an empty tree. In any non-empty tree:
1) There is one and only one specific node called the root (Root);
2) When n>1, the remaining nodes can be divided into m (m>0) mutual Disjoint finite sets T1, T2,..., Tn, each of which is a tree itself, and is called a subtree of the root.

In addition, the definition of the tree also needs to emphasize the following two points:
1) When n>0, the root node is unique, and there can be no multiple root nodes. The tree in the data structure can only have one root node.
2) When m>0, there is no limit to the number of subtrees, but they must be disjoint.
Example tree:
Figure 2.1 shows an ordinary tree:

Figure 2.1 Ordinary tree


It can be seen from the definition of the tree that the definition of the tree uses a recursive method. Recursion plays an important role in the learning process of the tree,

2.2 Degree of node

The number of subtrees a node has is called the degree of the node .
Figure 2.2 shows the degree of each node of the tree shown in Figure 2.1.

Figure 2.2 Schematic diagram of degrees

2.3 Node relationship

The root node of the node subtree is the child node of the node . The corresponding node is called the parent node of the child node .
In Figure 2.2, A is the parent node of B, and B is the child node of A.
The child nodes of the same parent node are called sibling nodes .
In Figure 2.2, node B and node C are sibling nodes.

2.4 Node level

Starting from the definition of the root, the root is the first level, the children of the root are the second level, and so on.
Figure 2.3 shows the hierarchical relationship of the tree shown in Figure 2.1

Figure 2.3 Schematic diagram of layers

2.5 Depth of the tree

The maximum number of levels of nodes in the tree is called the depth or height of the tree. The depth of the tree shown in Figure 2.1 is 4.

3 Binary tree

3.1 Definition

A binary tree is a finite set of n (n>=0) nodes. The set is either an empty set (called an empty binary tree), or consists of a root node and two disjoint trees, which are called root nodes. The left subtree and the right subtree are composed.
Figure 3.1 shows an ordinary binary tree:

Figure 3.1 Binary tree

3.2 Characteristics of Binary Tree

From the definition of the binary tree and graphical analysis, the binary tree has the following characteristics:
1) Each node has at most two subtrees, so there is no node with a degree greater than 2 in the binary tree.
2) The left subtree and the right subtree are in order, and the order cannot be reversed arbitrarily.
3) Even if a node in the tree has only one subtree, it is necessary to distinguish whether it is a left subtree or a right subtree.

3.3 Binary tree properties

1) There are at most 2i-1 nodes on the i-th level of the binary tree. (I>=1)
2) If the depth of the binary tree is k, then there are at most 2k-1 nodes. (k>=1)
3) n0=n2+1 n0 represents the number of nodes with degree 0, and n2 represents the number of nodes with degree 2.
4) In a complete binary tree, the depth of a complete binary tree with n nodes is [log2n]+1, where [log2n] is rounded down.
5) If a complete binary tree with n nodes is numbered from 1 to n from top to bottom and from left to right, any node numbered i in the complete binary tree has the following characteristics:

(1) i=1 , [i/2] ;
(2) 2i>n 2i
(3) 2i+1>n 2i+1

3.4

3.2

3.3

3.5



1
2 2
3

3.4

3.6

n i(1<=i<=n) i
3.5

3.5

Features :
1) Leaf nodes can only appear in the lowest and sub-lower layers.
2) The lowest leaf nodes are concentrated in the left part of the tree.
3) If there is a leaf node on the penultimate layer, it must be in a continuous position on the right.
4) If the node degree is 1, then the node has only the left child, that is, there is no right subtree.
5) For a binary tree with the same number of nodes, the depth of the complete binary tree is the smallest.
Note : A full binary tree must be a complete binary tree, but the reverse is not necessarily true.

3.7 Storage structure of binary tree

3.7.1 Sequential storage

The sequential storage structure of the binary tree is to use a one-dimensional array to store the nodes in the binary tree, and the storage location of the node is the subscript index of the array.

Figure 3.6

A complete binary tree shown in Figure 3.6 uses sequential storage, as shown in Figure 3.7:

Figure 3.7 Sequential storage

It can be seen from Figure 3.7 that when the binary tree is a complete binary tree, the number of nodes just fills the array.
So when the binary tree is not a complete binary tree, what about the sequential storage form? For example: for the binary tree described in Figure 3.8:

Figure 3.8.png

The light-colored node indicates that the node does not exist. Then the sequential storage structure of the binary tree shown in Figure 3.8 is shown in Figure 3.9:

Figure 3.9

Among them, means that there is no storage node at this position in the array. At this point, it can be found that there has been a waste of space in the sequential storage structure.
Then the sequential storage structure corresponding to the extreme case of the right-slant tree shown in Figure 3.3 is shown in Figure 3.10:

Figure 3.10

It can be seen from Figure 3.10 that for this extreme case of a right-slant tree, using sequential storage is a waste of space. Therefore, sequential storage is generally suitable for complete binary trees.

3.7.2 Binary Linked List

Since sequential storage cannot meet the storage requirements of a binary tree, chain storage is considered. From the definition of the binary tree, each node of the binary tree has at most two children. Therefore, the node data structure can be defined as one data and two pointer fields. The representation is shown in Figure 3.11:

Figure 3.11

Define the node code:

typedef struct BiTNode { TElemType Data; //data struct BiTNode * lchild , * rchild ;//left child pointers } BiTNode, *BiTree; Copy code

Then the binary tree shown in Figure 3.6 can be represented by Figure 3.12.

Figure 3.12

In Figure 3.12, a linked list structure is used to store the binary tree. This kind of linked list is called a binary linked list.

3.8 Binary tree traversal

The traversal of the binary tree is a key point of knowledge to be examined.

Recursive solution

Recursive solution is a more commonly used and easy to understand method, as long as you understand the idea, you can use it well.
**For example, pre-order traversal: **The recursive method of pre-order traversal is: root, left, and right , first print the root node, only then look for its left subtree, and when the left subtree finds the end, it returns and finds the index again. Until it's done.

Put the code below:

Preorder traversal

public static void PreOrderRecur (TreeNode root) { if (root == null ) return ; System.out.println(root.data); PreorderRecur(root.left); PreorderRecur(root.right); } Copy code

In-order traversal

public static void InOrderRecur (TreeNode root) { if (root == null ) return ; InorderRecur(root.left); System.out.println(root.data); InorderRecur(root.right); } Copy code

Post-order traversal

public static void PostOrderRecur (TreeNode root) { if (root == null ) return ; PostorderRecur(root.left); PostorderRecur(root.right); System.out.println(root.data); } Copy code

Observation shows that the realization of recursion is actually only the position of the output root node is different, and there is no big difference.

Iterative solution

Essentially, it is simulating recursion. Because the system stack is used in the recursion process, Stack is often used to simulate the system stack in the iterative solution. Pay attention to the first-in-last-out order of the stack, the output is printed in reverse order.

Preorder traversal

The preorder traversal order of the fork tree is root-left-right. We can use a stack to assist. We put the result of the pre-order traversal into an ArrayList container as the return value. The specific steps are as follows:
1. Put the root node root of the fork tree into the stack.
2, if the stack is not empty, is removed from the stack node, that node to discharge the tail START container; if the right Submenu tree of the node is not empty, then
the nodes that discharge START stack; if left Submenu the node If the tree is not empty, put the left subtree into the stack.
3. Repeat step 2 until the stack is empty, at which point the traversal ends. The code is as follows:

static List<Interger> PreOrderTraversal (TreeNode root) { List(Interger) result = new ArrayList<>(); Stack<TreeNode> stack = new Stack(); if (root == null ) return result; stack.push(root); //First put the root node into the stack while (!stack.isEmpty(){ //When the stack is not empty, perform the following operations TreeNode temp = stack.pop(); //Remove the node in the stack and save it with a temporary variable result.add(temp.val); //Add the value of the variable to the result queue if (tmp.right!= null ) stack.push(root.right); //If the right subtree of the node is not empty, put the node on the stack if (tmp.left!= null ) stack.push(root.left); //If the left subtree of the node is not empty, put the left subtree on the stack. } return result; } Copy code

In-order traversal

The middle-order traversal order of the fork tree is left-root-right. We can pick one uses one stack to assist, we have the result in the in-order traversal a
ArrayList container as the return value, the specific steps are as follows:
1, gets into the while loop, then the root node and all the nodes left Submenu discharge In the stack.
2. Take a node from the stack and place the node at the end of the container; if the right subnode of the node is not empty, put the right subnode and
all the left subnodes of its right subnode into the queue.
3. Repeat step 2 until the stack is empty and the current node is also empty, then exit the loop.
It might be a bit messy to read the explanation, just look at the code, it will be easier to understand with the code

code show as below:

public List<Integer> InOrderTraversal (TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { if (root != null ){ stack.push(root); root=root.left; } else { root = stack.pop(); res.add(root.data); root=root.right; } } return res; } Copy code

Subsequent traversal

Wide search + reverse order output = post-order traversal
The post-order traversal order of the fork tree is left-right-root. We can use a stack to assist, but it is still a bit different from pre-order traversal and middle-order traversal. We put the result of post-order traversal into a LinkedList container as the return value. The specific steps are as follows:
1. The root node root of the fork tree is placed on the stack.
2. If the stack is not empty, take a node from the stack and insert the node into the head of the container. ; If the left subtree of the node is not
empty, put the left subtree on the stack; if the right subtree of the node is not empty, put the right subtree on the stack. ,
Noted that the preamble and preorder traversal before, we are Using ArrayList container, and is to the node Insert the tail of the container, which
is, after traversing different points.
3. Repeat step 2 until the stack is empty, at which point the traversal ends and the
code is as follows:

public List<Integer> postOderTraversal (TreeNode root) { LinkedList<Integer> res = new LinkedList<>(); //Note, use the linked list Stack<TreeNode> stack = new Stack<>(); if (root == null ) return res; stack.push(root); while (!stack.isEmpty()) { TreeNode tmp = stack.pop(); //Note that it is placed in the first position res.addFirst(tmp.val); if (tmp.left != null ) stack.push(tmp.left); if (tmp.right != null ) stack.push(tmp.right); } return res; } Copy code

Sequence traversal

Please refer to my other blog post, link .

4 Conclusion

Through the above introduction, we have got a preliminary understanding of binary trees. The basic knowledge introduced in this article hopes that readers can grasp it firmly and build a binary tree model in their minds to lay a solid foundation for subsequent learning.