一、先序递归遍历(Preorder Recursive Traversal)
1.1 算法
首先需要明确的是这里的序是针对 root 节点而言的。故先序即先“访问”根节点,其次“访问”其左右节点。
1.2 图示
1.3 代码
Talk is cheap, show me the code! — Linus Benedict Torvalds
public void preOrder(Node<E> root){
if(root != null) {
System.out.print(root.data);
System.out.print('\t');
preOrder(root.lnode);
preOrder(root.rnode);
}
}
二、中序递归遍历(Inorder Recursive Traversal)
2.1 算法
从根节点 root 出发,先“访问”左子树(Left Subtree),当左子树的每个节点都“访问”完后,才访问根节点,最后“访问”右子树(Right Subtree)。
2.2 图示
2.3 代码
public void inOrder(Node<E> root){
if(root != null) {
//track to the deepest left branch
inOrder(root.lnode);
//visit the root node
System.out.print(root.data);
System.out.print('\t');
inOrder(root.rnode);
}
}
三、后序递归遍历(Postorder Recursive Traversal)
3.1 算法
根节点是最后“访问”的,不管是在根节点所在的整棵树,还是根节点以下的子树都是先“访问”左子树中的节点,其次是右子树中节点,最后“访问”根节点。
3.2 图示
3.3 代码
public void postOrder(Node<E> root){
if(root != null) {
//track to the deepest left branch
postOrder(root.lnode);
//track to the deepest right branch
postOrder(root.rnode);
//after visiting all the nodes of both left subtree and right subtree
System.out.print(root.data);
System.out.print('\t');
}
}
注意:层次遍历不能递归,可以结合递归条件想想为什么哦 🙂
keep reading ,keep learning, keep coding…