In the actual scene, there are often one-to-many or even many-to-many situations. Many logics are not simple linear relationships, and trees and graphs are typical nonlinear data structures.
The tree
What is a tree? There are many examples of tree logic in life:
In the data structure, a tree is defined as follows:
A tree is a finite set of n (n>=0) nodes. When n=0, it is called an empty tree. Any non-empty tree has the following characteristics:
1. There is only one specific node called root
2. When n > 1, the remaining nodes can be divided into M (m>0) finite sets that do not intersect each other, and each set itself is a tree, which is called the subtree of the root
Here’s a standard tree structure
In the figure above, node 1 is the root node, and nodes 5, 6, 7, 8 and 9 are the end of the tree without “children”, called leaf nodes. The dotted line in the figure is one of the subtrees of root node 1
At the same time, the structure of the tree is divided into different levels from root node to leaf node, and its relationship between upper and lower levels and peer nodes is as follows:
The upper level node of node 4 is the parent node of node 4, and the node derived from node 4 is the child node of node 4. The nodes derived from the same parent node are called the ** sibling nodes of node 4. The maximum number of levels in the ** tree is It’s called the height or depth of the tree, and the height of the tree above is 4
Binary tree
A binary tree is a tree with a maximum of two children per node. A binary tree is a tree with a maximum of two children per node
The structure of binary tree is shown as follows:
The two children of a binary tree node are called the left child and the right child in a fixed order
In addition, there are two special forms of binary tree: full binary tree and complete binary tree
Full binary tree
A binary tree in which all non-leaf nodes are left and right children and all leaf nodes are on the same level is a full binary tree
Complete binary tree
A binary tree with n nodes is numbered in hierarchical order, and all nodes are numbered from 1 to N. If all nodes in the tree are in the same position as nodes numbered from 1 to N in a full binary tree of the same depth, the binary tree is called a complete binary tree
The height of a complete binary tree is logn+1 rounded down (starting at 1)
The diagram below:
The binary tree is numbered from 1 to 12, which corresponds exactly to the nodes numbered from 1 to 12 in the previous full binary tree, so this tree is a complete binary tree
Data structure can be divided into physical structure and logical structure, binary tree belongs to logical structure, it can be expressed by a variety of physical structure (array, chain storage structure)
Chain storage structure
Each node of a binary tree contains three parts:
1. Data for storing data
2. The left pointer to the left child
3. The right pointer to the right child
An array of
When array storage is used, nodes in the binary tree are placed in their respective positions in the array in hierarchical order. If the left or right child of a node is empty, the corresponding position in the array is also empty
The goal is to make it easier to locate the child and parent nodes of the binary tree in the array
For example, if the subscript of a parent node is parent, then the subscript of its leftChild node is 2*parent+ 1, and the subscript of its right child node is 2*parent+2. Conversely, if the subscript of a leftChild node is leftChild, So its parent is (leftChild-1) / 2
Obviously for a sparse binary tree, using an array representation is a waste of space
Application of binary tree
Binary trees contain many special forms, each of which has its own purpose, but the most important applications are in lookup operations and maintaining relative order
To find the
Special binary tree: binary search tree
Binary search tree adds the following conditions on the basis of binary tree:
1. If the left subtree is not empty, the values of all nodes in the left subtree are smaller than those of the root node
2. If the right subtree is not empty, the values of all nodes in the right subtree are greater than those of the root node
3. Both the left and right subtrees are binary search trees
Here is a standard binary search tree:
For example, to find the node whose value is 4, perform the following steps:
1. Access root node 6 and discover that 4 is less than 6
2. Access node 3 on the left of node 6 and discover that node 4 is greater than node 3
3. Access node 4, the right child of node 3, and find that node 4=4
For a binary search tree with relatively balanced node distribution, if the total number of nodes is N, the time complexity of searching nodes is O(logn).
Maintain relative order
Binary search tree requires that the left subtree be smaller than the root node and the right subtree be larger than the root node, which ensures the order of the binary tree. Therefore, binary search tree has another name: binary sort tree
In the example above, a new node 5 is inserted. Since 5 < 6, 5 > 3, and 5 > 4, node 5 will be inserted to the right of the child of node 4
Insert a new node 10, and since 10 > 6, 10 > 8, and 10 > 9, node 10 will be inserted to the right of the child of node 9
Existing problems:
Insert 9, 8, 7, 6, 5, and 4 in the binary search tree
Not only the appearance becomes strange, the time complexity of query also becomes O(n), to solve this problem involves the self-balance of binary tree
Traversal of binary trees
Why didn’t we focus on traversal when we introduced arrays and linked lists
What’s special about traversal of binary trees
In computer programs, traversal is itself a linear operation, so traversing arrays and linked lists, which are also linear data structures, is a breeze
However, binary tree is a typical nonlinear data structure, and traversal requires the transformation of nonlinear associated nodes into a linear sequence. If traversal is performed in different ways, the sequence traversed will be different
Binary tree traversal
From the point of view of node position relation, the traversal of binary tree can be divided into four kinds
1. Preorder traversal
2. Middle order traversal
3. Back-order traversal
4. Sequence traversal
From a macro point of view, binary tree traversal can be divided into two categories
1. Depth-first traversal (pre-order traversal, mid-order traversal, post-order traversal)
2. Breadth-first traversal (sequence traversal)
Depth-first traversal
The concepts of depth first and breadth first are not limited to binary trees. They are abstract algorithmic ideas that determine the order of accessing some complex data structures.
The so-called depth-first, as the name implies, is biased in depth, “head to the bottom” access mode
1. Preorder traversal
Binary tree traversal, output order is: root node, left subtree, right subtree
Above is a binary tree foreorder traversal, the left serial number of each node represents the output order of the node, the detailed steps are as follows:
1. Output root node 1
2. Because root node 1 has a left child, output the left child node 2
3. Since node 2 also has left child, output left child node 4
4. Node 4 has neither left nor right children, so go back to node 2 and output node 5, the right child of node 2
5. Node 5 has neither left nor right children, so go back to node 1 and output node 3, the right child of node 1
6. Node 3 has no left child but a right child, so output node 6, the right child of node 3
2. Middle order traversal
Middle order traversal of binary tree, output order is: left subtree, root node, right subtree
Above is a binary tree middle order traversal, detailed steps are as follows
1. First access the left child of the root node. If the left child has left children, continue to access until the node no longer has left children, and output this node.
2. Output the parent node of node 4, node 2, in the order traversed in
3. Output node 5, the right child of node 2
4. After traversing the left subtree of node 2 as the root node, output node 1 as the root node of the entire binary tree
5. Since node 3 has no left child, output node 3, the right child of the root node
6. Finally, output node 6, the right child of node 3
3. Back-order traversal
The order of output is left subtree, right subtree and root node
Above is a binary tree after the order traversal, detailed steps are as follows:
1. Same as middle-order traversal, first visit the left child of the root node. If the left child has left children, continue to visit until the node that no longer has left children is found and output this node, then output node 4
2. According to the order of the traversal, then output the root node of node 4, the right child of node 2, node 5
3. Node 2 is the root node of node 4
4. The left subtree of root node 2 has been traversed. Next, access the right child of root node 1, node 3.
5. Access node 6 because node 3 has no left child.
6. Since node 6 has no left or right child, output node 6.
7. Output node 3, the root node of node 6
8. Output node 1, the root node of node 3
Depth-first traversal code implementation
Recursive implementation:
interface TreeNodeType{ data: any; leftChildren: TreeNodeType | null; rightChildren: TreeNodeType | null; } class TreeNode implements TreeNodeType{ data: any; leftChildren: TreeNodeType | null; rightChildren: TreeNodeType | null; constructor(params:any){ this.data = params; this.leftChildren = null; this.rightChildren = null; }} / * * * @ param {Array < any >} list * @ param {number} [index] to read nodes subscript * @ returns {(TreeNodeType | null)} * @ the description Function createBinaryTree(list:Array<any>, index? :number):TreeNodeType|null { if(! Array.isArray(list) || ! list.length){ return null } let node = null; let i = index || 0 let data = list[i]; if(data ! == undefined) { node = new TreeNode(data); node.leftChildren = createBinaryTree(list, i * 2 + 1); node.rightChildren = createBinaryTree(list, I * 2 + 2)} return node} / * * * @ param {(TreeNodeType | null)} node * @ the description the preamble of binary tree traversal * / function preOrderTraversal(node: TreeNodeType | null){ if(node === null){ return } console.log(node.data); preOrderTraversal(node.leftChildren); PreOrderTraversal (node rightChildren)} / * * * @ param {(TreeNodeType | null)} node * @ the description in the binary tree traversal * / function inOrderTraversal(node: TreeNodeType | null){ if(node === null){ return } inOrderTraversal(node.leftChildren); console.log(node.data); inOrderTraversal(node.rightChildren); } / * * * @ param {(TreeNodeType | null)} node * @ description sequence after the binary tree traversal * / function postOrderTraversal (node: TreeNodeType | null){ if(node === null){ return } postOrderTraversal(node.leftChildren); postOrderTraversal(node.rightChildren); console.log(node.data); } function main(){const a = createBinaryTree([1,2,3,4,5,6]); Console. log(' forward traversal '); preOrderTraversal(a); Console. log(' middle-order traversal '); InOrderTraversal (a) console.log(' post-traversal '); postOrderTraversal(a); Console. log(' stack implementation pre-order traversal '); preOrderTraversalByStack(a); Console. log(' breadth - OrderTraversal ') levelOrderTraversal(a)} main()Copy the codeThis is a change from the original book building binary tree implementation
The stack to achieve
Most of the problems that can be solved recursively can be solved using another data structure, the stack, because recursion and the stack both have backtracking properties,
The following is a binary tree traversal as an example to see the specific implementation process:
1. First traverse the root node 1 of the binary tree and add it to the stack
2. Traverse the root node 1, and add the left child node 2 to the stack
3. Iterate over the left child of node 2 and add node 4 to the stack
4. Node 4 has neither left child nor right child. In this case, we need to go back to node 2, that is, let the old top element 4 go off the stack, then we can revisit node 2 and get the right child of node 2, node 5. Node 2 is removed from the stack and node 5 is added
5. Node 5 has neither left nor right children, so we need to go back again, all the way back to node 1, so let node 5 go out of the stack, the right child of root node 1 is node 3, then node 1 goes out of the stack, and node 3 goes into the stack
6. If node 3 has no left child and node 6 has only the right child, node 3 is removed from the stack and node 6 is pushed
7. If node 6 has neither left child nor right child, node 6 is removed from the stack. At this point, the stack is empty and the traversal is complete
The code implementation is as follows
/ * * * @ param {TreeNode} node * @ description stack implementation preorder traversal * / function preOrderTraversalByStack (node: TreeNodeType | null) { if(node === null){ return } const stackList:Array<TreeNode> = []; let treeNode:TreeNodeType|null = node; while(treeNode ! == null || stackList.length) { while(treeNode ! == null) { console.log(treeNode.data) stackList.push(treeNode); treeNode = treeNode.leftChildren } if(stackList.length) { treeNode = <TreeNodeType>stackList.pop(); treeNode = treeNode.rightChildren } } }Copy the codeBreadth-first traversal
If depth-first traversal is “diving low” in one direction, breadth-first traversal is the opposite: take the first step in each direction, then take the second step in each direction,…. Until I’ve gone in every direction,
The following demonstrates breadth-first traversal through the sequential traversal of a binary tree
Hierarchical traversal, as its name implies, is the horizontal traversal of each node layer by layer in a binary tree according to the hierarchical relationship from root node to leaf node
The figure above is a binary tree sequence traversal node output order, to achieve such traversal, need to use a data structure: queue, detailed steps are as follows
1. The root node 1 enters the queue
2. Node 1 exits the queue, outputs node 1, obtains node 2 and node 3 of node 1, and makes node 2 and node 3 join the queue
3. Node 2 exits the team and obtains node 4, the left child of node 2, and node 5, the right child of node 2
4. Node 3 exits the queue and obtains node 6, the right child of node 3, so that node 6 can join the queue
5. Nodes 4, 5, and 6 are sent out of the team in sequence. As there are no child nodes, they do not join the team
Breadth-first traversal code implementation
/ * * * @ param {TreeNode} sequence traversal node * @ the description - breadth-first traversal * / function levelOrderTraversal (node: TreeNodeType | null) { if(node === null){ return } let queue:Array<TreeNode> = []; queue.push(node) while(queue.length) { let outNode = <TreeNodeType>queue.shift(); console.log(outNode.data) if(outNode.leftChildren) { queue.push(outNode.leftChildren) } if(outNode.rightChildren) { queue.push(outNode.rightChildren) } } }Copy the codeSummary from: the journey of cartoon algorithm xiao Grey algorithm