Article directory
-
- Binary tree definition
- How to traverse a binary tree
-
- Preorder traversal
-
- Recursive DFS
- Iteration (stack)
- inorder traversal
-
- Recursive DFS
- Iteration (stack)
- Postorder traversal
-
- Recursive DFS
- Iteration (stack)
- level-order traversal
-
- iterate(queue)
Definition of binary tree
Binary tree is a common tree-like data structure, which consists of a node called the root node (Root) and up to two pointers (left child node and right child node) pointing to other nodes.
static class TreeNode{<!-- -->
public char val;//node value
public TreeNode left; //Left child node
public TreeNode right;//right child node
public TreeNode(char val){<!-- -->//Node assignment
this.val = val;
}
public TreeNode(char val,TreeNode left,TreeNode right){<!-- -->//When assigning node values, specify the left and right children
this.val = val;
this.left =left;
this.right =right;
}
}
How to traverse a binary tree
- Create a binary tree:
public static TreeNode creatTree(){<!-- -->
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A;
}
The picture shows:
Preorder traversal
Preorder traversal (left and right of the root) A B D E H C F G
Recursive DFS
//Global list collection //Storage tree nodes
static List<TreeNode> list = new ArrayList<>();
// dfs depth-first recursion
private static void dfs(TreeNode root) {<!-- -->
if(root == null) return;//Used for null test, also used as recursive exit
list.add(root);//root
dfs(root.left);//left
dfs(root.right);//right
}
Iteration (stack)
Method 1
//Global list collection //Storage tree nodes
static List<TreeNode> list = new ArrayList<>();
/**
* Iteration method 1 + stack
* Preorder traversal is around the root. First save the root node, then pop it off the stack, and then put the value into the list.
* Then enter the right node, enter the left node and repeat the cycle,
* That is, the left node is treated as the root node for operation (that is, the left subtree is operated), and the right subtree is operated after the left subtree is operated.
*/
private static void iteration1(TreeNode root) {<!-- -->
if (root == null) return;
Deque<TreeNode> stack= new LinkedList<>();
stack.push(root);//Push the root node onto the stack
while(!stack.isEmpty()){<!-- -->
root = stack.pop();//pop the traversed nodes
list.add(root);
//Push the right child node onto the stack first, and then push the left child node onto the stack, so that the left child node will be accessed first when popping it off the stack.
if(root.right != null) stack.push(root.right);
if(root.left != null) stack.push(root.left);
}
}
Method 2 (recommended)
//Global list collection //Stores the nodes of the tree
static List<TreeNode> list = new ArrayList<>();
/**
* Iteration method 2 + stack
* Enter the root and then enter the left until there is no left, then pop the top of the stack (find the leftmost node),
* Then find the right child of the leftmost node. At this time, the right child is the root node. Then loop the operation.
* Key points: After the root node and left node are processed, treat the right node as the root node and start the operation from the beginning of the loop (that is, organize the entire right subtree).
*/
private static void iteration(TreeNode root) {<!-- -->
if (root == null) return;
Deque<TreeNode> stack= new LinkedList<>();
while(!stack.isEmpty() || root != null){<!-- -->
while(root != null){<!-- --> // The left node is always pushed onto the stack and added to the list at the same time
list.add(root);
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;//Switch the right node to continue looping
}
}
In-order traversal
In-order traversal (left root right) D B E H A F C G
Recursive DFS
//Global list collection //Storage tree nodes
static List<TreeNode> list = new ArrayList<>();
/**
* dfs recursive in-order traversal
*
*/
private static void dfs(TreeNode root) {<!-- -->
if(root == null) return;
dfs(root.left);
list.add(root);
dfs(root.right);
}
Iteration (stack)
Method 1
//Global list collection //Storage tree nodes
static List<TreeNode> list = new ArrayList<>();
/**
* Iteration method one + stack
*/
private static void iteration(TreeNode root) {<!-- -->
if (root == null) return;
Deque<TreeNode> stack = new LinkedList<>();
while(!stack.isEmpty() || root != null){<!-- -->//Note that the stack may be empty. At this time, the left subtree of root has been traversed and continues to traverse root.right, so the condition root must be added. != null
if (root != null) {<!-- --> // Pointer to access the node, access to the lowest level
stack.push(root);//Put the visited node into the stack
root = root.left; // left
}else {<!-- -->
root = stack.pop();
list.add(root); // Medium
root = root.right; // right
}
}
Method 2 (recommended)
//Global list collection //Storage tree nodes
static List<TreeNode> list = new ArrayList<>();
/**
* Iteration method two + stack
*/
private static void iteration1(TreeNode root) {<!-- -->
if (root == null) return;
Deque<TreeNode> stack = new LinkedList<>();
while(!stack.isEmpty() || root != null) {<!-- -->//Note that the stack may be empty. At this time, the left subtree of root has been traversed and continue to traverse root.right, so the condition root must be added. != null
while(root != null){<!-- -->
stack.push(root);
root = root.left;//Access the left subtree node to the lowest level
}
root = stack.pop();//If the left subtree of the node is null, pop up and add to the list
list.add(root);
root = root.right;//Then access the left subtree of the pop-up node
}
}
Post-order traversal
Postorder traversal (left and right roots) D H E B F G C A
Recursive DFS
//Global list collection //Stores the nodes of the tree
static List<TreeNode> list = new ArrayList<>();
/**
* dfs postorder recursion (left and right roots) D H E B F G C A
*/
private static void dfs(TreeNode root) {<!-- -->
if(root == null) return;
dfs(root.left);//left
dfs(root.right);//right
list.add(root);//root
}
Iteration (stack)
Method 1
//Global list collection //Stores the nodes of the tree
static List<TreeNode> list = new ArrayList<>();
/**
* Iteration method 1 + stack (improved on pre-order traversal, exchange the order in which the left and right children of pre-order traversal are pushed into the stack, get the root right and left, and then reverse it, which is post-order traversal)
*/
private static void iteration1(TreeNode root) {<!-- -->
if(root == null) return;
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty() ){<!-- -->
root = stack.pop();
list.add(root);
if(root.left != null) stack.push(root.left);//Compared to pre-order traversal, this changes the stacking order so that the right node pops out of the stack first (root right left---> left and right roots)
if(root.right != null) stack.push(root.right);
}
//What we get above is actually the reverse order of post-order traversal, so just reverse the list and it will be post-order traversal (root right and left ---> left and right roots)
Collections.reverse(list);
}
Method 2 (recommended)
/**
* Iteration method two + stack
* Keep pushing the middle left into the stack until there is no left side, and then check whether the top node of the stack has a right node. If not, pop it out of the stack and put it into the vector.
* Otherwise, the right node is used as the root node to recycle (that is, the right part is directly treated as a tree).
*/
private static void iteration(TreeNode root) {<!-- -->
if (root == null) {<!-- -->
return ;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {<!-- -->
while (root != null) {<!-- -->
stack.push(root);
root = root.left;
}
TreeNode peekNode = stack.peek();
if (peekNode.right != null & amp; & amp; peekNode.right!= prev) {<!-- -->
// If the right child node exists and has not been visited, process the right subtree
root = peekNode.right;
} else {<!-- -->
// Otherwise, it means that the left and right subtrees have been processed and the current node can be accessed.
list.add(peekNode);
prev = stack.pop();//Record the popped node, which is used to determine whether the right child node has been processed the next time the node is processed.
}
}
}
Level-order traversal
Level order traversal A B C D E F G H
Iteration (queue)
/**
* iteration + queue
* @param root
*/
private static void iteration(TreeNode root) {<!-- -->
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();//queue
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
int size = queue.size();//Record the number of nodes in each layer
for (int i = 0; i < size; i + + ) {<!-- -->//Get the nodes of each layer
root = queue.poll();
list.add(root);
if(root.left != null) queue.offer(root.left);//If the child node of the current node is not empty, add it
if(root.right != null) queue.offer(root.right);
}
}
}